Kõige tähtsam masin, mida kunagi ei ehitatud

Arvutamine on tuttav mõiste, millest enamik meist intuitiivselt aru saab. Võtke funktsioon f(x) = x + 3. Millal x on kolm, f(3) = 3 + 3. Kuus. Lihtne. Tundub ilmne, et see funktsioon on arvutatav. Kuid mõned funktsioonid ei ole nii lihtsad ja pole nii lihtne kindlaks teha, kas neid saab arvutada, mis tähendab, et need ei pruugi kunagi anda meile lõplikku vastust.

1928. aastal pakkusid saksa matemaatikud David Hilbert ja Wilhelm Ackermann välja küsimuse, mida nimetatakse Entscheidungsprobleem ("otsuse probleem"). Aja jooksul viiks nende küsimus arvutatavuse ametliku määratluseni, mis võimaldas matemaatikutel vastata paljudele uutele probleemidele ja pani aluse teoreetilisele arvutiteadusele.

Määratlus pärines 23-aastaselt Alan Turingilt, kes kirjutas 1936. põhjalik paber mis mitte ainult ei vormistanud arvutamise kontseptsiooni, vaid osutus ka matemaatika põhiküsimuseks ja lõi intellektuaalse aluse elektroonilise arvuti leiutamisele. Turingi suurepärane arusaam oli anda arvutusküsimusele konkreetne vastus abstraktse masina kujul, mille tema doktoriõppe nõunik Alonzo Church nimetas hiljem Turingi masinaks. See on abstraktne, kuna see ei eksisteeri (ja ei saagi) füüsiliselt käegakatsutava seadmena eksisteerida. Selle asemel on see arvutamise kontseptuaalne mudel: kui masin suudab funktsiooni arvutada, on see funktsioon arvutatav.

See toimib järgmiselt. Turingi masin suudab lugeda ja muuta sümboleid lõpmatult pikal lindil, nagu reeglite tabel ette näeb. Lint koosneb rakkudest, kuhu saab salvestada täpselt ühe sümboli ning masin loeb ja kirjutab lindipeaga lahtrite sisu ümber. Iga tabeli reegel määrab, mida masin peaks tegema nii oma praeguse oleku kui ka loetava sümboli põhjal. Masin võib siseneda lõppolekusse ("accept state" või "reject state"), mille järel see peatub, nõustudes või lükates tagasi sisendi. Või satub see lõpmatusse ahelasse ja jätkab lindi lugemist igavesti.

Parim viis Turingi masina mõistmiseks on vaadelda lihtsat näidet. Kujutagem ette üht, mis on mõeldud meile ütlema, kas antud sisend on number null. Kasutame sisendnumbrit 0001 koos tühjade sümbolitega (#), nii et „#0001#” on meie lindi asjakohane osa.

Masin käivitub algolekus, mida me nimetame q0-ks. See loeb meie lindi kõige vasakpoolsemat lahtrit ja leiab tühja ruumi. Reeglid ütlevad: "Kui olekus q0 on sümbol #, jätke see muutmata kujule, liigutage üks lahter paremale ja muutke masina olekuks q1." Pärast seda sammu on masin olekus q1 ja selle pea loeb teist sümbolit 0.

Nüüd otsime reeglit, mis kehtib nende tingimuste kohta. Leiame ühe, mis ütleb: "Jää olekusse q1 ja liigutage pead ühe lahtri võrra paremale." See jätab meid samasse asendisse (olekus q1, näit “0”), nii et liigume edasi paremale, kuni pea loeb lõpuks teistsuguse numbri, 1.

Tabelit uuesti uurides leiame uue reegli: "Kui kohtame 1, siis üleminek q2-le, mis on tagasilükkamise olek." Masin peatub ja vastab "Ei" algsele küsimusele "Kas '0001' on null?"

Kui selle asemel on sisend "#0000#", näeb masin pärast kõiki neid nulle #. Kui vaatame tabelit, leiame reegli, mis ütleb, et see tähendab, et masin siseneb olekusse q3, "aksepteerimisolekusse". Nüüd vastab masin "Jah" küsimusele "Kas "0000" on null?

Oma abstraktse masinaga koostas Turing arvutusmudeli, et vastata Entscheidungs-probleemile, mis formaalselt küsib: kas matemaatiliste aksioomide komplekti arvestades on olemas mehaaniline protsess – juhiste kogum, mida tänapäeval nimetaksime algoritmiks –, mis saab alati kindlaks teha, kas antud väide vastab tõele?

Ütleme, et tahame leida algoritmi, mis ütleb meile, kas teatud maleasend on võimalik. Siin on aksioomid malereeglid, mis reguleerivad seaduslikke käike. Kas me saame sellesse positsiooni jõudmiseks järgida piiratud samm-sammult protseduuride jada? Kuigi mõne positsiooni analüüsimiseks võib kuluda kauem kui meie eluea jooksul – algoritm võib genereerida kõik võimalikud positsioonid ja võrrelda neid sisendiga –, on sellised algoritmid malemängus olemas. Selle tulemusena ütleme, et male on "otsustav".

Kuid 1936. aastal tõestasid Church ja Turing – kasutades erinevaid meetodeid – iseseisvalt, et Entscheidungs-probleemi iga juhtumi lahendamiseks ei ole üldist viisi. Näiteks mõned mängud, nagu John Conway elumäng, on otsustamatud: ükski algoritm ei saa kindlaks teha, kas teatud muster ilmub esialgse mustri põhjal.

Turing näitas, et funktsioon on arvutatav, kui on olemas algoritm, mis suudab soovitud ülesande täita. Samas näitas ta, et algoritm on protsess, mida saab defineerida Turingi masinaga. Seega on arvutatav funktsioon funktsioon, mille arvutamiseks on Turingi masin. See võib tunduda keerulise viisina arvutatavuse määratlemiseks, kuid see on parim, mis meil on. "See ei ole nii, et teil on valik seda mingil muul viisil määratleda," ütles Michael Sipser, Massachusettsi Tehnoloogiainstituudi teoreetiline arvutiteadlane. "Ma arvan, et on üldiselt aktsepteeritud, et Church-Turingi väitekiri ütleb, et algoritmi mitteametlik mõiste vastab sellele, mida iga "mõistlik" arvutusmudel suudab teha. Teised matemaatikud on välja pakkunud erinevaid arvutusmudeleid, mis näevad pealtnäha üsna erinevad, kuid on tegelikult samaväärsed: nad saavad teha mis tahes arvutusi, mida suudavad Turingi masinad, ja vastupidi.

Vaid paar aastat pärast seda, kui Kurt Gödel oli tõestanud, et matemaatika on mittetäielik, Church ja Turing näitasid selle tööga, et mõned matemaatikaprobleemid on lahendamatud – ükski algoritm, olgu see nii keerukas, ei suuda meile öelda, kas vastus on jah või ei. Mõlemad olid laastavad löögid Hilbertile, kes oli lootnud, et matemaatika annab selged ja idealiseeritud vastused. Kuid võib-olla on see sama hästi: kui Entscheidungs-probleemile oleks olemas üldine lahendus, tähendaks see, et kõik matemaatika probleemid saaks taandada lihtsateks mehaanilisteks arvutusteks.

Lisaks neile põhiküsimustele vastamisele viis Turingi masin universaalse Turingi masinana tuntud variandi kaudu ka otse kaasaegsete arvutite väljatöötamiseni. See on eriline Turingi masin, mis suudab mis tahes sisendil simuleerida mis tahes teist Turingi masinat. See suudab lugeda teiste Turingi masinate kirjeldusi (nende reegleid ja sisendlinte) ja simuleerida nende käitumist oma sisendlindil, tekitades sama väljundi, mida simuleeritud masin toodaks, nagu tänapäeva arvutid suudavad lugeda mis tahes programme ja seda käivitada. 1945. aastal pakkus John von Neumann välja arvutiarhitektuuri, mida nimetatakse von Neumanni arhitektuuriks, mis tegi universaalse Turingi masina kontseptsiooni võimalikuks reaalses elus.

Kui Sanjeev Arora, Princetoni ülikooli teoreetiline arvutiteadlane, õpetab seda kontseptsiooni, ta rõhutab laiemat filosoofilist pilti. "Universaalsel on kaks mõistet," ütles ta. "Üks idee universaalsest on see, et see võib töötada mis tahes muu Turingi masinaga. Kuid teine, suurem mõiste "universaalne" on see, et see võib käivitada mis tahes arvutusi, mille te universumis välja mõtlete. Klassikalise füüsika maailmas saab iga füüsikalist protsessi modelleerida või simuleerida algoritmide abil, mida omakorda saab simuleerida Turingi masina abil.

Teine tähelepanuväärne ja üha kasulikum variant on tõenäosuslik Turingi masin. Erinevalt tavalisest Turingi masinast – millel on igale sisendile täpselt määratletud reaktsioon – võib tõenäosuslikul Turingi masinal olla tõenäosustel põhinevaid mitmeid reaktsioone. See tähendab, et see võib erinevatel aegadel anda sama sisendi jaoks erinevaid tulemusi. Üllataval kombel selline tõenäosuslik strateegia võib teatud probleemide puhul olla tõhusam kui puhtalt deterministlik lähenemine. Tõenäosuslike Turingi masinate ideed on osutunud praktiliselt kasulikuks sellistes valdkondades nagu krüptograafia, optimeerimine ja masinõpe.

Need abstraktsed masinad on ehk parim tõend selle kohta, et fundamentaalsete küsimuste esitamine võib olla üks kõige kasulikumaid asju, mida teadlane teha saab.