Hugur - 01.01.1995, Qupperneq 94

92
Atli Harðarson
HUGUR
stærðfræðilegum hætti og orða aðferð til að herma eftir þeim ef slík
lýsitig er gefin. Turingvél sem vinnur eftir þessari aðferð getur því
hermt eftir öllum öðrum Turingvélum. Slík vél er kölluð altæk
Turingvél (universal Turing machine). Turing gat sér þess til að
altæk Turingvél geti reiknað öll reiknanleg föll. Með þessari tilgátu
setti hann fram skilgreiningu á reiknanleika. Samkvæmt henni er
reiknanlegt fall það sama og fall sem Turingvél getur reiknað.
Turing gat ekki sannað að vélarnar sem hann smíðaði í huga sér
gætu reiknað allt sem stærðfræðingar hafa fundið upp eða munu fínna
upp aðferðir til að reikna. En hann gat sér þess til. Um svipað leyti
settu Emil Post og Alonso Church, hvor í sínu lagi, fram skil-
greiningar á reiknanleika sem síðar var sannað að væru jafngildar
skilgreiningu Turing. Bæði af því að þessar skilgreiningar eru allar
jafngildar og af því að engum hefur tekist að benda á fall sem menn
gætu hugsanlega reiknað en fellur ekki undir þær má telja nær fullvíst
að hér sé um að ræða réttar skilgreiningar á reiknanleika. Það má þá
líka telja nær fullvíst að vélarnar sem Turing hugsaði sér, og vani er
að kalla Turingvélar, geti reiknað allt sem hægt er að reikna.
Sú tilgáta að skilgreiningar þeirra Church, Post og Turing fangi
eðli reiknanleikans, þannig að undir þær falli öll reiknanleg föll, er
kölluð tilgáta Church og Turing. Ég geng að því sem vísu að hún sé
sönn.
Tölvur geta gert allt sem altæk Turingvél getur svo það er hægt að
láta tölvur framkvæma alla mögulega útreikninga.7 Hvernig tengist
þetta mannlegum vitsmunum? Vél sem getur unnið eftir hvaða
reikniaðferð sem er getur ef til vill slegið fólki við í reikningi - en
fólk getur gert svo ótal margt annað en að reikna. Er nokkur ástæða
til að ætla að hægt sé að fá tölvur til að herma eftir annars konar
hugarstarfí en því sem byggist á einhvers konar útreikningum?
Hér þurfum við að huga að því hvað átt er við með tali um
reiknanleg föll. Fall tekur við táknum, þ.e. tölum, stöfum, orðum,
merkjum eða munstrum af einhverju tagi og skilar táknum þannig að
7 Hér þarf að bæta við einum fyrirvara. Turing hugsaði sér að vélamar sínar
hefðu óendanlega langan tíma og óendanlega mikið pláss fyrir útreikninga á
pappírsstrimlinum. Hngin tölva endist endalaust og engin tölva hefur óendanlega
stórt vinnsluminni. Það er því sama hvaða tölvu er bent á, ef við vitum
endingartíma hennar og vinnslurými þá getum við fundið reikningsdæmi sem hún
ræður ekki við.