Mașină Turing

Mașinile Turing sunt mecanisme extrem de elementare de dispozitive de prelucrare a simbolurilor care — în ciuda simplității lor — pot fi adaptate pentru a simula logica oricărui calculator ce poate fi construit. Modelele au fost descrise în 1936 de către Alan Turing. Deși modelele erau proiectate inițial pentru a fi fezabile din punct de vedere tehnic, mașinile Turing nu au fost gândite pentru a fi tehnologii practice de calcul, ci un experiment mental despre limitele calculului mecanic; astfel, ele nu au fost niciodată construite. Studiul proprietăților lor abstracte este util în informatică și teoria complexității.
O mașină Turing capabilă de a simula orice altă mașină Turing se numește mașină Turing universală (sau mașină universală). O definiție mai orientată matematic a fost introdusă de Alonzo Church, ale cărui lucrări din domeniul calculului lambda s-au împletit cu cele ale lui Turing într-o teorie formală a calculului cunoscută sub numele de Conjectura Church-Turing. Aceasta postulează că orice problemă de calcul bazată pe o procedură algoritmică poate fi rezolvată de către o mașină Turing. Deoarece nu se bazează pe o definiție precisă a conceptului de procedură algoritmică, nu are o formulare matematică. În schimb, este posibil de a se defini o noțiune de "sistem acceptabil de programare" și de a se demonstra că "puterea de calcul" a unui asemenea sistem este echivalentă cu cea a unei mașini Turing (se vorbește în acest caz de un limbaj de programare Turing-complet).
La origine, conceptul de mașină Turing reprezenta o persoană virtuală executând o procedură bine definită, schimbând conținutul căsuțelor unui tablou infinit (vizualizat sub forma unei "benzi" infinite), plasând în aceste căsuțe simboluri luate dintr-un ansamblu finit de simboluri. Pe de altă parte, această persoană trebuie să memoreze "starea" în care se află sistemul (sistemul "persoană" poate ocupa un număr finit de "stări"). Procedura poate fi exemplificată de o manieră foarte simplă printr-o listă de instrucțiuni, de genul : dacă sunteți în starea 42 și dacă simbolul din căsuța pe care o priviți este '0', atunci înlocuiți acest simbol printr-un '1', treceți în starea 17, și priviți căsuța alăturată (dreapta sau stânga) .
O mașină Turing este echivalentă cu un automat cu stivă modificat prin relaxarea constrângerii de last-in-first-out a stivei acestuia. (Interesant este că această relaxare aparent minoră permite mașinii Turing să execute o largă varietate de calcule, astfel încât ea poate servi ca model pentru capabilitățile computaționale ale tuturor software-urilor moderne.)
Mai exact, o mașină Turing constă din:
De notat că toate componentele mașinii sunt finite; doar cantitatea nelimitată de bandă îi dă acesteia un volum nelimitat de spațiu.
O mașină Turing este de obicei definită ca un 6-tuplu M = (Q,Γ,s,b,F,δ), unde
Definițiile din literatura de specialitate diferă uneori, pentru a face demonstrațiile mai ușoare sau mai clare, dar aceasta se face întotdeauna de așa natură încât mașina să-și păstreze puterea computațională. De exemplu, schimbarea mulțimii {L,R} în {L,R,S}, unde S permite mașinii să stea pe aceeași celulă a benzii în loc să se deplaseze la stânga sau la dreapta, nu mărește puterea computațională a mașinii.
O mașină Turing cu k benzi poate fi și ea descrisă ca un 6-tuplu M = (Q,Γ,s,b,F,δ), unde
De notat că o mașină Turing cu k benzi nu este mai puternică decât o mașină Turing standard.
Următoarea mașină Turing are un alfabet {'0', '1'}, cu 0 simbol vid. Ea așteaptă o serie de '1' pe bandă, cu capul inițial pe cel mai din stânga 1, și dublează simbolurile 1 punând un 0 între ele, de exemplu "111" devine "1110111". Mulțimea de stări este {s1, s2, s3, s4, s5} și starea inițială este s1. Tabela de acțiuni este următoarea.
Seria de calcule pentru această mașină Turing ar fi: (poziția capului e indicată prin simbol îngroșat)
Comportamentul acestei mașini poate fi descris de o buclă: Începe în S1, înlocuiește primul 1 cu 0, apoi folosește S2 pentru a se muta la dreapta, sărind peste 1-uri și peste primul 0 întâlnit. S3 sare apoi peste următoarea secvență de 1-uri (inițial nu există nici una) și înlocuiește primul 0 găsit cu un 1. S4 mută capul înapoi la stânga, sărind peste 1-uri până găsește un 0 după care trece în S5. S5 mută capul la stânga, sărind peste 1-uri până când găsește 0-ul scris la început de S1. Înlocuiește acel 0 cu un 1, avansează o poziție la dreapta și trece din nou în S1 pentru o nouă rundă a buclei. Aceasta continuă până când S1 găsește un 0 (anume 0-ul din mijlocul celor două șiruri de 1) moment în care mașina se oprește.
Dacă tabela de acțiuni are cel mult o intrare pentru fiecare combinație simbol-stare atunci mașina este o mașină Turing deterministă (MTD). Dacă tabela de acțiuni conține mai multe intrări pentru cel puțin o combinație simbol-stare atunci mașina este o mașină Turing nedeterministă (MTND sau MTN). Cele două sunt computațional echivalente, adică orice MTND se poate transforma într-o MTD (și invers).
Fiecare mașină Turing calculează o funcție parțială calculabilă din șirurile de intrare peste alfabetul ei. Din acest punct de vedere, se comportă exact ca un calculator cu un program fixat. Totuși, putem codifica tabela de acțiuni a oricărei mașini Turing într-un șir. Astfel, putem construi o mașină Turing care așteaptă pe banda ei un șir care descrie o tabelă de acțiuni urmată de un șir care descrie banda de intrare, și apoi calculează banda pe care mașina Turing astfel codificată ar calcula-o. Turing a descris o astfel de construcție în lucrarea sa din 1936.
În 1947, Turing a spus:
Cu această codificare a tabelei de acțiuni ca șir de simboluri, devine în principiu posibil ca mașinile Turing să răspundă la întrebări despre comportamentul altor mașini Turing. Majoritatea acestor întrebări, însă, sunt nedecidabile, adică funcția în chestiune nu poate fi calculată mecanic. De exemplu, problema determinării dacă o anume mașină Turing se oprește sau nu la o anumită intrare, sau la orice intrare, problemă cunoscută și sub numele de problema opririi, s-a demonstrat că este, în general, nedecidabilă în lucrarea originală a lui Turing. Teorema lui Rice arată că orice întrebare netrivială despre comportamentul sau ieșirea unei mașini Turing este nedecidabilă.
Dacă în definiția "mașinii Turing universale" includem orice mașină Turing care simulează un model computațional Turing-complet, și nu doar mașinile Turing care simulează direct alte mașini Turing, o mașină Turing universală poate fi relativ simplă, folosind doar câteva stări și câteva simboluri. De exemplu, e nevoie de doar 2 stări, deoarece se cunoaște o mașină Turing universală de 2×18 (adică 2 stări, 18 simboluri).
De ceva timp, cele mai mici mașini Turing universale cunoscute, care simulau un model computațional numit sistem de etichetare, avea următoarele numere de stări și simboluri : 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2. (De exemplu, vezi Minsky Cap 14.8.1 p. 277 pentru o descriere detaliată a unei mașini 4×7 bazate pe sistemul de etichetare.) Wolfram descrie în cartea sa, A New Kind of Science, o mașină Turing universală cu 2 stări și doar 5 simboluri, care emulează un automat celular de asemenea considerat universal, făcând aceasta cea mai simplă mașină Turing universală cunoscută.
O mașină Turing universală este Turing-completă. Poate calcula orice funcție recursivă, decide orice limbaj recursiv, și accepta orice limbaj recursiv enumerabil. Conform conjecturii Church-Turing, problemele rezolvabile de o mașină Turing universală sunt exact acele probleme rezolvabile de un algoritm sau de o metodă efectivă de calcul, pentru orice definiție rezonabilă a acestor termeni.
O versiune abstractă a mașinii Turing universale este funcția universală, o funcție calculabilă care poate fi utilizată pentru a calcula orice altă funcție calculabilă. Teorema utm demonstrează existența acestei funcții.