Þessi Turing vél ætti að keyra að eilífu nema stærðfræði sé röng

Hundrað og fimmtíu ára stærðfræði mun reynast röng ef nýtt tölvuforrit hættir að keyra. Sem betur fer er ólíklegt að það gerist, en kóðinn á bak við það reynir á takmörk stærðfræðisviðsins.

Forritið er hermt Turing vél, stærðfræðilegt reiknilíkan búið til af kóðabrjótur Alan Turing. Árið 1936 sýndi hann fram á að hægt er að líkja eftir aðgerðum hvaða tölvualgríms sem er með einfaldri vél sem les og skrifar 0 og 1 á óendanlega langa spólu með því að vinna í gegnum mengi ástands, eða leiðbeiningar. Því flóknara sem reikniritið er, því fleiri ástand þarf vélin.

Nú hafa Scott Aaronson og Adam Yedidia frá Massachusetts Institute of Technology búið til þrjár Turing vélar með hegðun sem er fléttuð inn í djúpar spurningar um stærðfræði. Þetta felur í sér sönnun hins 150 ára gamla Riemann tilgáta – talið stjórna mynstrum frumtalna.

Vélar Turing hafa lengi verið notaðar til að rannsaka slíkar spurningar. Uppruni þeirra liggur í röð heimspekilegra opinberana sem skóku stærðfræðiheiminn á þriðja áratug síðustu aldar. Í fyrsta lagi sannaði Kurt Gödel að sumar stærðfræðilegar fullyrðingar er aldrei hægt að sanna sannar eða rangar – þau eru óákveðin. Hann bjó í rauninni til stærðfræðilega útgáfu af setningunni „Þessi setning er röng“: rökrétt heilabrot sem stangast á við sjálfan sig.

Engin sönnun fyrir öllu

Fullyrðing Gödels er með brottfallsákvæði. Ef þú breytir grunnforsendunum sem sönnunargögnin eru byggð á – fræðiheitunum – geturðu gert vandamál illskiljanlegt. En það mun samt skilja eftir önnur vandamál sem eru óákveðin. Það þýðir að það eru engin öfugmæli sem gera þér kleift að sanna allt.

Í kjölfar röksemda Gödels, sannaði Turing að það hljóta að vera einhverjar Turing-vélar sem ekki er hægt að spá fyrir um hegðun þeirra samkvæmt stöðluðu meginorði – þekktur sem Zermelo-Fraenkel mengikenningin með aðalatriði valsins (C), eða öllu heldur ZFC – sem liggur til grundvallar flestum stærðfræði. En við vissum ekki hversu flóknar þær þyrftu að vera.

Nú hafa Yedidia og Aaronson búið til Turing vél með 7918 fylkjum sem hefur þessa eiginleika. Og þeir hafa nefnt það „Z“.

„Við reyndum að gera það áþreifanlegt og segja hversu mörg ríki þarf áður en þú kemst í þetta hyldýpi ósannanleikans? segir Aronson.

Parið hermdi eftir Z á tölvu, en það er nógu lítið til að það gæti fræðilega verið byggt sem líkamlegt tæki, segir Terence Tao frá Kaliforníuháskóla í Los Angeles. „Ef maður myndi síðan kveikja á slíkri líkamlegri vél, þá teljum við að myndi gerast að hún myndi ganga endalaust,“ segir hann og gerir ráð fyrir að þú hunsar líkamlegt slit eða orkuþörf.

Enginn endir í sjónmáli

Z er hannað til að fara í gegnum 7918 leiðbeiningarnar að eilífu, en ef það hætti á endanum myndi það reynast ZFC ósamræmi. Stærðfræðingar myndu þó ekki vera of örvæntingarfullir – þeir gætu einfaldlega skipt yfir í örlítið sterkara sett af aðalsetningum. Slík axiom eru þegar til og hægt er að nota þau til að sanna hegðun Z, en það er lítið að græða á því vegna þess að það verður alltaf Turing vél sem fer yfir hvaða axiom sem er.

„Maður getur hugsað sér hvert tiltekið kerfi sem er eins og tölva með ákveðið takmarkað magn af minni eða vinnsluorku,“ segir Tao. „Maður gæti skipt yfir í tölvu með enn meira geymsluplássi, en sama hversu mikið geymslupláss tölvan hefur, þá verða samt nokkur verkefni sem eru umfram getu hennar.“

En Aaronson og Yedidia hafa búið til tvær aðrar vélar sem gætu gefið stærðfræðingum meira hlé. Þetta mun aðeins hætta ef tvö fræg stærðfræðileg vandamál, sem lengi hafa verið talin vera sönn, eru í raun röng. Þetta eru tilgáta Goldbachs sem segir að hver slétt heil tala stærri en 2 sé summa tveggja frumtalna og Riemann tilgátan sem segir að allar frumtölur fylgi ákveðnu mynstri. Hið síðarnefnda er grunnur að hluta nútíma talnafræði og að afsanna hana væri mikil, ef ólíkleg, uppnámi.

Hagnýtir kostir

Reyndar hafa parið ekki í hyggju að keyra Turing vélarnar sínar endalaust til að reyna að sanna að þessi vandamál séu röng. Það er ekki sérlega skilvirk leið til að ráðast á það vandamál, segir Lance Fortnow hjá Georgia Institute of Technology í Atlanta.

Að tjá stærðfræðileg vandamál sem Turing vélar hefur annan hagnýtan ávinning: það hjálpar til við að finna út hversu flóknar þær eru. Goldbach vélin hefur 4888 fylki, Riemann-vélin hefur 5372, en Z hefur 7918, sem bendir til þess að ZFC vandamálið sé flóknasta af þessum þremur. “Það myndi passa við innsæi flestra um þessa tegund af hlutum,” segir Aaronson.

Yedidia hefur sett kóðann sinn á netið og stærðfræðingar gætu nú keppt við að minnka stærð þessara Turing véla og þrýsta þeim til hins ýtrasta. Þegar umsagnaraðili á bloggi Aaronson segist hafa búið til 31-ríkis Goldbach vél , þó að parið hafi enn ekki staðfest þetta.

Fortnow segir að raunveruleg stærð Turing vélanna skipti engu máli. „Blaðið segir okkur að við getum haft mjög þjappaðar lýsingar sem þegar fara út fyrir kraft ZFC, en jafnvel þótt þær væru þjappaðari myndi það ekki gefa okkur mikið hlé á grunni stærðfræðinnar,“ segir hann.

En Aaronson segir að það að minnka Z frekar gæti sagt eitthvað áhugavert um takmörk undirstöðu stærðfræði – eitthvað sem Gödel og Turing hafa líklega viljað vita. „Þeir gætu hafa sagt „þetta er fínt, en geturðu fengið 800 fylki? Hvað með 80 fylki?’“ segir Aaronson. „Mig langar að vita hvort það sé til 10 ríkja vél þar sem hegðun hennar er óháð ZFC.

Tilvísun: http://www.scottaaronson.com/busybeaver.pdf