Mașinile Turing explicate

În 1936, înainte să existe computere electronice, matematicianul Alan Turing, în vârstă de 24 de ani, s-a întrebat ce înseamnă ca un calcul să fie mecanic. Răspunsul lui a fost o mașină imaginară atât de simplă încât abia dacă ar putea face mai puțin: citește și scrie simboluri pe o bandă, câte o celulă pe rând, după un tabel fix de reguli. S-a dovedit că această mașină definește însăși noțiunea de calcul, iar ea a arătat că la unele întrebări niciun computer nu va putea răspunde vreodată.

O bandă de celule cu cifre de 1 și celule goale, cu un cap de citire-scriere deasupra unei celule, etichetat cu starea sa
O bandă de celule cu cifre de 1 și celule goale, cu un cap de citire-scriere deasupra unei celule, etichetat cu starea sa

Întrebarea lui Turing

În 1928, David Hilbert a întrebat dacă există o procedură mecanică ce decide, pentru orice enunț al matematicii, dacă poate fi demonstrat: Entscheidungsproblem. Pentru a răspunde, cineva trebuia să spună exact ce este o procedură mecanică. În articolul său din 1936, On Computable Numbers, Turing și-a imaginat un funcționar care lucrează cu creionul pe hârtie și a redus munca la pașii ei cei mai mici: privești un simbol, îl schimbi, treci la un simbol vecin și ții minte puțin din ce făceai. Rezultatul a fost mașina Turing.

O mașină Bombe (stânga) și un portret al lui Alan Turing (dreapta)
O mașină Bombe (stânga) și un portret al lui Alan Turing (dreapta)

Mașina

O mașină Turing are o bandă împărțită în celule, nesfârșită în ambele direcții, fiecare celulă conținând un simbol, de obicei gol. Un cap stă pe o celulă, iar mașina se află într-una dintr-un număr finit de stări. Un tabel de reguli indică, pentru fiecare stare și fiecare simbol pe care capul îl poate citi, simbolul de scris, direcția de deplasare și starea următoare. Mașina aplică o regulă la fiecare pas. Când intră într-o stare de oprire, se oprește, iar ce a rămas pe bandă este răspunsul ei.

Programe ca tabele de reguli

Fiecare tabel de reguli este un program. Pentru a aduna 1 la un număr binar, mașina merge la capătul din dreapta al numărului, apoi se deplasează spre stânga transformând cifrele de 1 în 0 până găsește un 0 sau o celulă goală, pe care o transformă în 1. Pentru a verifica dacă un cuvânt este palindrom, șterge primul simbol, îl reține în starea sa, aleargă la celălalt capăt și verifică dacă ultimul simbol se potrivește, apoi repetă. Programele lungi, cum ar fi unul care înmulțește sau sortează, sunt construite din aceleași câteva tipuri de reguli.

Mașina universală

Cea mai importantă idee a lui Turing a fost că tabelul de reguli însuși poate fi scris pe bandă. O mașină Turing universală citește descrierea oricărei alte mașini și intrarea acesteia, apoi o imită pas cu pas. O singură mașină fixă poate deci rula orice program: acesta este principiul din spatele oricărui computer cu program stocat, în care software-ul este doar date în memorie. Orice sistem care poate imita o mașină Turing universală se numește Turing-complet, inclusiv orice limbaj de programare, Jocul vieții al lui Conway și automatul celular Regula 110.

Teza Church–Turing

În același an, Alonzo Church a descris calculul prin calculul lambda, iar cele două definiții s-au dovedit a calcula exact aceleași funcții. La fel s-a întâmplat cu fiecare model de mai târziu, de la mașinile cu registre la procesoarele moderne. Teza Church–Turing afirmă că tot ce poate fi calculat printr-o procedură pas cu pas poate fi calculat de o mașină Turing. Ea nu poate fi demonstrată, deoarece „procedură pas cu pas” este o noțiune informală, dar nu s-a găsit niciodată vreun contraexemplu.

Problema opririi

Turing a arătat apoi că unele întrebări nu au un răspuns mecanic. Să presupunem că o mașină ar putea decide, pentru orice program și orice intrare, dacă acel program se oprește până la urmă. Construiți un program nou care întreabă acest decident despre el însuși și apoi face opusul: dacă i se spune că se oprește, ciclează la nesfârșit, iar dacă i se spune că ciclează, se oprește. Oricare răspuns este greșit, deci decidentul nu poate exista. Problema opririi este indecidabilă și, odată cu ea, Entscheidungsproblem: niciun algoritm nu poate rezolva orice întrebare matematică.

Castori harnici

În 1962, Tibor Radó a transformat problema opririi într-un joc: dintre toate mașinile cu n stări și simbolurile 0 și 1 care se opresc când pornesc pe o bandă goală, care scrie cele mai multe cifre de 1 și câți pași poate face o astfel de mașină? Aceste numere, valorile castorului harnic, cresc mai repede decât orice funcție calculabilă, deoarece o metodă de a le calcula ar rezolva problema opririi. Valorile cunoscute sunt 6, 21 și 107 pași pentru două, trei și patru stări; pentru cinci stări, campionul lui Heiner Marxen și Jürgen Buntrock face 47.176.870 de pași, valoare demonstrată în 2024 de colaborarea online bbchallenge printr-o demonstrație verificată de computer. Pentru șase stări se cunosc mașini care fac mai mulți pași decât se pot scrie în notația obișnuită.

Explorați

Deschideți simulatorul de mașină Turing pentru a rula opt programe gata făcute sau pentru a scrie propriul program. Urmăriți capul pas cu pas și vedeți ce regulă se aplică, priviți contorul care nu se oprește niciodată, verificați palindroame și rulați castorii harnici: cei 107 pași ai campionului cu patru stări încap în diagramă, iar cei 47 de milioane de pași ai campionului cu cinci stări durează câteva secunde la viteza maximă.

Întrebări frecvente

A fost construită vreodată mașina Turing?

Nu așa cum a descris-o Turing, deoarece banda ei este nesfârșită, dar ideea a fost urmată curând de computere reale cu program stocat, la proiectarea cărora a contribuit chiar Turing după al Doilea Război Mondial. De atunci, pasionații au construit modele funcționale din lemn, din LEGO și chiar în Jocul vieții, toate cu o bandă finită, ceea ce ajunge pentru orice calcul care se termină.

Care este diferența dintre numerele de pași 14 și 21 pentru trei stări?

Există două întrebări despre castorii harnici: cele mai multe cifre de 1 scrise și cei mai mulți pași făcuți. Pentru trei stări, mașina din simulator scrie maximum șase cifre de 1 în 14 pași, în timp ce o altă mașină cu trei stări face maximum 21 de pași, dar lasă doar cinci cifre de 1. Pentru două, patru și cinci stări, o singură mașină câștigă la ambele.

Înseamnă Turing-complet puternic?

Înseamnă capabil să calculeze orice este calculabil, cu suficient timp și memorie, ceea ce nu spune nimic despre viteză. O mașină Turing are nevoie de mulți pași pentru aritmetica simplă, iar unele sisteme sunt Turing-complete aproape din întâmplare, cum ar fi jocurile de cărți, formulele din foile de calcul și redstone-ul din Minecraft.

De ce nu poate un computer să ruleze pur și simplu un program pentru a vedea dacă se oprește?

Rularea arată că un program se oprește, dacă se oprește, dar dacă nu s-a oprit încă, nu puteți ști dacă nu se va opri niciodată sau are doar nevoie de mai mult timp. Demonstrația lui Turing arată că nicio metodă mai ingenioasă nu funcționează pentru orice program, deși pentru multe programe anume se poate răspunde la întrebare.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Deschide simulatorul de mașină Turing