Tärkein kone, jota ei koskaan rakennettu

Laskenta on tuttu käsite, jonka useimmat meistä ymmärtävät intuitiivisesti. Ota funktio f(x) = x + 3. Milloin x on kolme, f(3) = 3 + 3. Kuusi. Helppo. Näyttää ilmeiseltä, että tämä funktio on laskettavissa. Mutta jotkut funktiot eivät ole niin yksinkertaisia, eikä ole niin helppoa määrittää, voidaanko ne laskea, mikä tarkoittaa, että ne eivät ehkä koskaan anna meille lopullista vastausta.

Vuonna 1928 saksalaiset matemaatikot David Hilbert ja Wilhelm Ackermann ehdottivat kysymystä nimeltä Entscheidungsprobleemi ("päätösongelma"). Aikanaan heidän kysymyksensä johtaisi laskettavuuden muodolliseen määritelmään, jonka avulla matemaatikot pystyivät vastaamaan lukuisiin uusiin ongelmiin ja loi pohjan teoreettiselle tietojenkäsittelytieteelle.

Määritelmä tuli 23-vuotiaalta jatko-opiskelijalta nimeltä Alan Turing, joka kirjoitti vuonna 1936 peruspaperi joka ei vain muotoillut laskennan käsitettä, vaan osoittautui myös matematiikan perustavanlaatuiseksi kysymykseksi ja loi älyllisen perustan elektronisen tietokoneen keksinnölle. Turingin suuri oivallus oli antaa konkreettinen vastaus laskentakysymykseen abstraktin koneen muodossa, jonka hänen tohtorintutkintonsa Alonzo Church myöhemmin nimesi Turingin koneeksi. Se on abstrakti, koska se ei ole (eikä voi) fyysisesti olla olemassa konkreettisena laitteena. Sen sijaan se on käsitteellinen laskentamalli: Jos kone voi laskea funktion, funktio on laskettavissa.

Näin se toimii. Turingin kone voi lukea ja muuttaa symboleja äärettömän pitkällä nauhalla sääntötaulukon mukaisesti. Nauha koostuu "soluista", joihin kukin voi tallentaa täsmälleen yhden symbolin, ja kone lukee ja kirjoittaa uudelleen solujen sisällön nauhapäällä. Jokainen taulukon sääntö määrittää, mitä koneen tulee tehdä sekä sen nykyisen tilan että sen lukeman symbolin perusteella. Kone voi siirtyä lopulliseen tilaan ("accept state" tai "reject state"), jossa se pysähtyy ja hyväksyy tai hylkää syötteen. Tai se putoaa äärettömään silmukkaan ja jatkaa nauhan lukemista ikuisesti.

Paras tapa ymmärtää Turingin konetta on tarkastella yksinkertaista esimerkkiä. Kuvitellaan yksi, joka on suunniteltu kertomaan meille, onko tietty syöte luku nolla. Käytämme syötenumeroa 0001 tyhjien symbolien (#) kanssa, joten "#0001#" on olennainen osa nauhaamme.

Kone käynnistyy alkutilassa, jota kutsutaan nimellä q0. Se lukee nauhamme vasemmanpuoleisimman solun ja löytää tyhjän tilan. Säännöt sanovat: "Kun tilassa q0, jos symboli on #, jätä se sellaisenaan ilman muutoksia, siirrä yksi solu oikealle ja muuta koneen tilaksi q1." Tämän vaiheen jälkeen kone on tilassa q1 ja sen pää lukee toista symbolia, 0.

Nyt etsimme sääntöä, joka koskee näitä ehtoja. Löydämme sellaisen, joka sanoo: "Pysy tilassa q1 ja siirrä päätä yksi solu oikealle." Tämä jättää meidät samaan asentoon (tilassa q1, lukema "0"), joten jatkamme liikkumista oikealle, kunnes pää lopulta lukee toisen luvun, 1.

Kun tarkastelemme taulukkoa uudelleen, löydämme uuden säännön: "Jos kohtaamme 1, siirrymme q2:een, joka on "hylkäämis"-tila. Kone pysähtyy ja vastaa "Ei" alkuperäiseen kysymykseen "Onko '0001' nolla?"

Jos sen sijaan syöte on "#0000#", kone näkee #-merkin kaikkien nollien jälkeen. Kun tarkastelemme taulukkoa, löydämme säännön, jonka mukaan tämä tarkoittaa, että kone siirtyy tilaan q3, "hyväksy"-tilaan. Nyt kone vastaa "Kyllä" kysymykseen "Onko '0000' nolla?"

Abstraktilla koneellaan Turing loi laskentamallin vastaamaan Entscheidungs-ongelmaan, joka muodollisesti kysyy: Kun otetaan huomioon joukko matemaattisia aksioomeja, onko olemassa mekaanista prosessia – käskysarjaa, jota nykyään kutsuisimme algoritmiksi – joka voi aina selvittää, onko jokin väite totta?

Oletetaan, että haluamme löytää algoritmin, joka voi kertoa meille, onko tietty shakkipaikka mahdollinen. Tässä aksioomit ovat shakin sääntöjä, jotka ohjaavat laillisia liikkeitä. Voimmeko noudattaa rajallista vaiheittaista prosessisarjaa päästäksemme tähän kohtaan? Vaikka joidenkin paikkojen analysointi voi kestää kauemmin kuin meidän elinaikamme – algoritmi voi luoda kaikki mahdolliset paikat ja verrata niitä syötteeseen – sellaisia ​​algoritmeja on shakkipeleissä. Tämän seurauksena sanomme, että shakki on "pääteltävissä".

Kuitenkin vuonna 1936 Church ja Turing - eri menetelmiä käyttäen - osoittivat itsenäisesti, ettei ole olemassa yleistä tapaa ratkaista Entscheidungs-ongelman jokaista tapausta. Esimerkiksi jotkut pelit, kuten John Conwayn Game of Life, ovat ratkaisemattomia: Mikään algoritmi ei voi määrittää, näkyykö tietty kuvio alkuperäisestä kuviosta.

Turing osoitti, että funktio on laskettavissa, jos on olemassa algoritmi, joka voi suorittaa halutun tehtävän. Samalla hän osoitti, että algoritmi on prosessi, joka voidaan määritellä Turingin koneella. Näin ollen laskettava funktio on funktio, jolla on Turingin kone sen laskemiseen. Tämä saattaa tuntua kierteiseltä tavalta määritellä laskettavuus, mutta se on paras, mitä meillä on. "Ei sinulla ole valinnanvaraa määritellä se jollain muulla tavalla", sanoi Michael Sipser, teoreettinen tietotekniikan tutkija Massachusetts Institute of Technologysta. "Mielestäni on yleisesti hyväksyttyä, että Church-Turingin teesi sanoo, että epävirallinen algoritmin käsite vastaa sitä, mitä mikä tahansa "järkevä" laskennallinen malli voi tehdä." Muut matemaatikot ovat keksineet erilaisia ​​laskentamalleja, jotka näyttävät pinnalta aivan erilaisilta, mutta ovat todellisuudessa samanarvoisia: He voivat tehdä minkä tahansa laskennan, jonka Turingin koneet voivat tehdä, ja päinvastoin.

Vain muutama vuosi sen jälkeen, kun Kurt Gödel oli todistanut matematiikan olevan epätäydellinen, Church ja Turing osoittivat tällä työllä, että jotkin matematiikan ongelmat ovat ratkaisemattomia – mikään algoritmi, olipa se kuinka kehittynyt tahansa, ei voi kertoa meille, onko vastaus kyllä ​​vai ei. Molemmat olivat tuhoisia iskuja Hilbertille, joka oli toivonut matematiikan saavan siistejä, idealisoituja vastauksia. Mutta se on ehkä aivan yhtä hyvä: Jos Entscheidungs-ongelmaan olisi olemassa yleinen ratkaisu, se tarkoittaisi, että kaikki matematiikan ongelmat voitaisiin pelkistää yksinkertaisiksi mekaanisiksi laskelmiksi.

Näihin peruskysymyksiin vastaamisen lisäksi Turingin kone johti myös suoraan nykyaikaisten tietokoneiden kehittämiseen universaalina Turingin koneena tunnetun muunnelman kautta. Tämä on erityinen Turingin kone, joka voi simuloida mitä tahansa muuta Turingin konetta millä tahansa syötteellä. Se voi lukea kuvauksia muista Turingin koneista (niiden säännöistä ja syöttönauhoista) ja simuloida niiden käyttäytymistä omalla syöttönauhallaan tuottaen saman tulosteen, jonka simuloitu kone tuottaisi, aivan kuten nykyiset tietokoneet voivat lukea mitä tahansa ohjelmaa ja suorittaa sen. Vuonna 1945 John von Neumann ehdotti tietokonearkkitehtuuria - nimeltään von Neumann -arkkitehtuuri, joka teki universaalin Turingin konekonseptin mahdolliseksi tosielämän koneessa.

Kun Sanjeev Arora, Princetonin yliopiston teoreettinen tietojenkäsittelytieteilijä, opettaa tätä käsitettä, hän korostaa laajempaa filosofista kuvaa. "Universaalisuudesta on kaksi käsitettä", hän sanoi. "Yksi käsite universaalista on, että se voi käyttää mitä tahansa muuta Turingin konetta. Mutta toinen, suurempi käsite 'universaalista' on, että se voi suorittaa mitä tahansa laskelmaa, jonka tulet keksimään universumissa. Klassisen fysiikan maailmassa mitä tahansa fyysistä prosessia voidaan mallintaa tai simuloida algoritmien avulla, joita puolestaan ​​voidaan simuloida Turingin koneella.

Toinen merkittävä ja yhä hyödyllisempi muunnos on todennäköisyyspohjainen Turingin kone. Toisin kuin tavallisella Turingin koneella – jolla on tarkasti määritelty reaktio jokaiseen syötteeseen – todennäköisyyspohjaisella Turingin koneella voi olla useita todennäköisyyksiin perustuvia reaktioita. Tämä tarkoittaa, että se voi tuottaa eri tuloksia samalle syötteelle eri aikoina. Yllättäen tällainen todennäköisyysstrategia voi olla tehokkaampi kuin puhtaasti deterministinen lähestymistapa tiettyihin ongelmiin. Todennäköisyyspohjaisten Turing-koneiden ideoiden on osoitettu olevan käytännössä hyödyllisiä sellaisilla aloilla kuin kryptografia, optimointi ja koneoppiminen.

Nämä abstraktit koneet ovat ehkä paras todiste siitä, että perustavanlaatuisten kysymysten esittäminen voi olla hyödyllisimpiä asioita, joita tiedemies voi tehdä.