Gödel, Turing og lélegasti ritari í heimi

Þessi færsla er sjálfstætt framhald af greinunum Rúllukragar og svartigaldur og Að spila Angry Birds, annar hluti: Þegar tannhjólið hitti logratöfluna. 

M.C. Escher, Hendur í teikningu

„Þessi setning er ósönn.“

Hvernig tengist þessi einfalda setning upphafi tölvualdar? Svarið liggur í því hvernig þversögn á borð við þessa vísar í sjálfa sig. Í baráttu stærðfræðinga við mótsagnir komust þeir að raun um að viss ímynduð kerfi mundu óhjákvæmilega geta vísað í sig sjálf — en ekki aðeins það, heldur önnur hlistæð kerfi líka. Því má halda fram að þaðan hafi fæðst nútímahugtakið um tölvuna.


Að tala um sjálfan sig — og aðra

Um aldamótin 1900 var í hámæli meðal stærðfræðinga að formgera stærðfræðina. Þetta fólst í því að smíða — í grófum dráttum — rökfærslukerfi þar sem allar útleiðslur væru agnarsmáar og óvefengjanlegar út frá nokkrum fyrirfram ákveðnum forsendum. Viðamesta tilraunin kom líklega frá Bertrand Russell og Alfred N. Whitehead: Principia Mathematica — gefin út á árunum 1910-1913 í þremur ritum og eitthvað vel á annað þúsund blaðsíðum sem litu að mestu svona út (þetta er bláendirinn á útleiðslu þess að 1+1=2):

Sagt er* að þrír prófarkarlesarar hafi sagt upp störfum og einn hengt
sig kringum útgáfu Principia Mathematica.
(*Sá sem segir það er ég. Ég veit ekki betur en að það sé lygi.)

Vandinn var í fyrsta lagi að hafa kerfið altækt og í öðru lagi mótsagnalaust. Með öðrum orðum bæði nógu öflugt til að geta (að minnsta kosti með „nægum“ tíma og þolinmæði) svarað öllum „vel saman settum“ spurningum með annaðhvort „satt“ eða „ósatt“ og hins vegar að aldrei mætti fá bæði svarið „satt“ og „ósatt“ við sömu spurningunni.

Þversagnir eins og þessi hér efst voru óvinurinn og það vissi Russell. Helsta einkenni slíkra þversagna er að þær fela í sér eins konar „afturbeygingu“ — þær bíta í skottið á sér. Með það í huga lagði Russell upp með að útrýma slíkum afturbeygingum með ýmsum reglum.

Kurt Gödel

En 1931 gaf rétt hálfþrítugur austurrískur rökfræðingur út grein sem sneri öllu á hvolf. Greinin hét, í lauslegri íslenskri þýðingu: Formlega óákvarðanlegar setningar í „Principia Mathematica“ og tengdum kerfum. Rökfræðingurinn hét Kurt Gödel.

Kjarninn í grein Gödels var þessi: Ef kerfi af þessu tagi er nógu öflugt til að vera yfirhöfuð tækur kostur má „umrita“ fullyrðingar um það sjálft á máli sem það ræður við.

Nánar tiltekið: Lágmarkskrafa til svona kerfis er að með því sé hægt að orða vissar fullyrðingar um heiltölur og svo meðhöndla þær (Til dæmis: Ef x og y eru báðar stærri en 0 er margfeldið x·y stærra en 0.) — en þar lá líka hundurinn grafinn.

Undir kerfi af þessu tagi þarf í upphafi að sættast á tákn (gætu verið stafir í stafrófinu eða yfirhöfuð hvað sem höfundinum dettur í hug) en Gödel sá að það mætti alveg eins nota runur af tölustöfum. Til dæmis mætti ákveða að 11 stæði fyrir „+“ og 12 stæði fyrir „=“ og svo framvegis.

Með þessu móti gat hann umritað fullyrðingar með tölum og — það sem meira var — hann gat látið reikningsaðferðir koma í staðinn fyrir reglurnar sem leyfðar eru í útleiðslum. Til dæmis má skeyta saman táknum með margföldun og samlagningu: 11·100+12 gæfi töluna 1112, sem hér stæði fyrir (að vísu merkingarlausa) strenginn „+=“.

Þetta kann að virðast ómerkilegt en með þessum hætti náði Gödel að sýna að öll kerfi af þessu tagi gætu fullyrt um sig sjálf (að vísu líka öll önnur kerfi af sömu gerð) og sýndi fram á eftirfarandi (með svolítilli einföldun):

1. Ef formlegt kerfi af þessu tagi uppfyllir lágmarkskröfur er annaðhvort hægt að leiða út mótsögn (til dæmis „himinninn er blár“ og „himinninn er ekki blár“) eða þá að hægt er að orða fullyrðingar sem hvorki er hægt að sanna né afsanna.
2. Ef kerfið er mótsagnalaust er ekki hægt að sanna að það er mótsagnalaust.

Þetta var alger katastrófa. Stærðfræðingar voru (og eru enn) tilneyddir að vinna með kerfi sem þeir vissu ekki fyrir víst hvort fæli í sér mótsagnir.

En þegar einar dyr lokast opnast aðrar: Nú var orðin til skýr hugmynd um það hvernig með tölum og einföldum reikniaðferðum mátti smíða og meðhöndla flóknar fullyrðingar sem fóru langt út fyrir svið reiknings. Tölvunarfræðin var tilbúin að fæðast.


Maður, bók og stór pappírsrúlla

Alan Turing

Í kjölfar greinar Gödels kom út — árið 1937 — grein eftir annan ungan stærðfræðing, Alan Turing að nafni (Turing var þá rétt óorðinn 24 ára). Greinin komst að tengdri og álíka bjartsýnislegri niðurstöðu: Til eru verkefni sem ekki eru leysanleg í endanlega mörgum skrefum. (Formlega tekur þetta til reiknirita (e. algorithms) en heimspekinga og rökfræðinga greinir á um hversu víðtæk niðurstaðan er.)

(Það ber að nefna að árið áður gaf Alonzo Church, bandarískur stærðfræðingur, út sönnun á sömu niðurstöðu. Hans tæki og tengsl hans við tölvunarfræðina eru litlu eða engu síður merkileg en framlag Turings en ég læt mér nægja að tala um Turing hérna.)

Þar sem Gödel og aðrir stærðfræðingar höfðu notast við svokölluð formleg mál til þess að tákna kerfi sín fann Turing upp aðra hugmynd — ímyndaða vél — sem hafði fullkomlega hliðstæða eiginleika en hafði þann kost að hún var aðeins hársbreidd frá raunverulegri vél. Hún kallast Turing-vél og virkar svona:

Ímyndið ykkur mann — reikningsmann (í síðustu grein minntist ég á að þessi stétt manna var þá nefnd á ensku computers) — í herbergi. Hann situr við skrifborð með blýant, strokleður, gríðarlangan pappírsborða með afmörkuðum reitum í einni röð — og bók. En þessi tiltekni reikningsmaður á við ákaflega sértæka námsörðugleika að stríða. Hann getur aðeins þekkt örfá tákn og öll fyrirmæli sem gætu talist hið minnsta flókin eða tvíræð eru honum ofviða. Svo til þess að fá hann til að vinna vinnuna sína þarf að gefa honum ákaflega einföld fyrirmæli. Í bókinni eru því aðeins fyrirmæli á borð við þessi:

Lína 22:
Ef o: Skrifaðu x þess í stað, farðu einn reit til hægri, flettu upp línu 12
Ef x: Skrifaðu x þess í stað, farðu einn reit til vinstri, flettu upp línu 23
Lína 23:
Ef o: Skrifaðu x þess í stað, farðu einn reit til hægri, flettu upp línu 12
Ef x: Skrifaðu o þess í stað, farðu einn reit til vinstri, flettu upp línu 11

Með öðrum orðum fullkomlega einhlít, ótvíræð og hundleiðinleg fyrirmæli upp á einn einasta staf í einu. En þetta var hugmynd Turings og hún var frábær.

Hugtakið um Turing-vél leyfir að önnur tákn séu notuð en o og x (hefðbundið væri að nota 0 og 1) en nokkuð sem lesandinn kann að átta sig á er að fjöldi tákna skiptir ekki öllu máli. Ef við þurfum allt íslenska stafrófið og tölustafina má t.d. nota sex stafa runur af o og x:

ooooox = 1
ooooxo = 2
ooooxx = 3
...
ooxoxo = A
ooxoxx = B
ooxxoo = C
ooxxox = D

og svo framvegis...

Þótt ótrúlegt megi virðast nægir þessi „vél“ til þess að framkvæma hvaða reikninga sem er, svo lengi sem notandinn getur sýnt natni við að semja fyrirmælin og umrita inntakið. (Fyrirmælin eru það sem stendur í bókinni; inntakið er það sem stendur á borðanum þegar maðurinn byrjar á vinnu sinni.) Og eins og Gödel hafði sýnt svo óþægilega fram á, þá ná „reikningar“ langt út fyrir einfalda reikninga.

Reikningarnir gætu til dæmis falist í að fara yfir textarunu og kanna hvort orðið „sprengja“ kemur fyrir eða jafnvel að bera saman langan texta við stafsetningarorðabók og kanna hvort öll orðin finnast í orðabókinni. Það má jafnvel kóða mynd — depil fyrir depil — á borðann og láta reikningsmanninn breyta myndinni. Þetta krefðist vissulega þykkrar bókar og langs borða en þetta er samt í grunnatriðum það sem tölvur gera fyrir okkur á hverjum degi — og það með hlistæðum hætti.

(Turing setti fram tilgátu sem í dag er yfirleitt kölluð Turing-Church-tilgátan: Hún segir fyrir um að allar „vélrænar“ aðgerðarunur megi framkvæma með svona vél. Hún er tilgáta en ekki lögmál því hún er líklega ekki beinlínis sannanleg frekar en eðlisfræðilögmálin; aðeins sannreynanleg. Enn og aftur greinir heimspekinga og aðra á um hversu víðtæk sú fullyrðing getur verið. Sér í lagi er deiluefni hvort mannsheilann megi skoða sem Turing-vél).

Í grein Turings birtist svo algerlega frábær hugmynd:

Hægt er að búa til Turing-vél — þ.e. með því að skrifa fyrirmælin í bókina með réttum hætti — sem getur líkt eftir hvaða Turing-vél sem er.

Þannig má, ef fyrirmælin í bókinni eru rétt skrifuð, umkóða lýsingu á nýjum fyrirmælum og skrifa á borðann. Til dæmis má skrifa fyrirmælin hér að ofan með þessum hætti:

22:o;x,H,12:x;x,V,23
23:o;x,H,12:x;o,V,11

og umrita svo í ásættanlega runu af o og x og láta svo það sem mundi vera inntakið í nýju Turing-vélina á eftir því.

Sem sagt: Fyrst stendur á bandinu hvað vélin á að gera við rununa sem kemur á eftir og síðan kemur runan.

Þetta er kannski hálfóskiljanlegt svo ég skal reyna að útskýra: Bókin og maðurinn eru saman vélbúnaðurinn í tölvunni. Í flestum tölvum væri ígildi bókarinnar harðkóðað: Til að breyta fyrirmælunum í bókinni þarf að taka fram vír og lóðbolta. En þetta sneiðir hjá því. Með svona Turing-vél er hægt að gefa karlinum við skrifborðið ný fyrirmæli með engu nema borðarúllu og penna — eða gataspjöldum — eða lyklaborði. Forritið fær að vera á sama stað og gögnin.


Rafræni ritarinn

Þegar búið er að smækka hugmynd um reikniverk niður í þetta öreindaform er ekki lengur svo erfitt að ímynda sér að rafbúnaður gæti framkvæmt þessi skref. Allt sem þarf er að búa til vél sem getur lesið muninn á x og o (eins og Turing ímyndaði sér vélina var borðinn í raun segulband), og látið litla rofa í sér verka þannig að x og o sé skrifað á réttum stöðum.

Þetta er hugmyndin um Turing-lokaða vél: Vél sem getur líkt eftir hvaða Turing-vél sem er. Og sú hugmynd er í dag notuð sem grundvallarpróf fyrir það hvort tölva er tölva — eða bara ómerkileg reiknivél.

Vart þarf að taka fram að í þessari mynd kæmi Turing-vélin sjálf að litlu gagni: Jafnvel einfaldir reikningar tækju óratíma; það væri líklega ráðlegra að ráða reikningsmann sem gæti hugsað upp á eigin spýtur. En brátt gat Turing-vélin nýtt sér snerpu rafeindatækninnar með notkun útvarpslampa og — enn síðar — smárans (e. transistor). Afraksturinn liggur meðal annars í tækinu sem þú notar nú til að lesa þennan texta.