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.^[1]^[2] 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.^[3]

O reprezentare artistică a unei *Mașini Turing*.

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).

Definiție

Descriere informală

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:

O bandă împărțită în celule aflate una lângă cealaltă. Fiecare celulă conține un simbol dintr-un alfabet finit. Alfabetul conține un simbol special vid (notat aici cu '0') și unul sau mai multe alte simboluri. Banda se presupune ca fiind extensibilă arbitrar la stânga și la dreapta, adică mașina Turing are întotdeauna suficientă bandă pentru a-și efectua calculele. Celulele care nu au fost scrise anterior se presupune că sunt ocupate cu simbolul vid.
Un cap care poate scrie și citi simboluri pe sau de pe bandă, și care se poate deplasa la stânga sau la dreapta
Un registru de stare care stochează starea mașinii Turing. Numărul stărilor diferite este întotdeauna finit și există o stare inițială cu care este inițializat registrul de stare.
O tabelă de acțiuni (sau funcție de tranziție) care spune mașinii ce simbol să scrie, cum să deplaseze capul ('L' pentru stânga, și 'R' pentru dreapta) și care va fi noua sa stare, date fiind simbolul citit de pe bandă și starea curentă. Dacă nu există intrare în tabela de acțiuni pentru combinația curentă de simbol citit și stare a sistemului, atunci mașina se oprește.

De notat că toate componentele mașinii sunt finite; doar cantitatea nelimitată de bandă îi dă acesteia un volum nelimitat de spațiu.

Definiție formală

Mașină Turing cu o singură bandă

O mașină Turing este de obicei definită ca un 6-tuplu M = (Q,Γ,s,b,F,δ), unde

$Q$ este o mulțime finită de stări
$\Gamma$ este alfabetul finit al simbolurilor de pe bandă
$s\in Q$ este starea inițială
$b\in \Gamma$ este simbolul vid (singurul simbol care are voie să existe pe bandă în număr nelimitat și singurul care poate fi pe bandă în orice moment)
$F\subseteq Q$ este mulțimea stărilor finale (sau acceptante)
$\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ este o funcție parțială numită funcția de tranziție, unde L este deplasarea la stânga și R este deplasarea la dreapta.

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.

Mașină Turing cu k benzi

O mașină Turing cu k benzi poate fi și ea descrisă ca un 6-tuplu M = (Q,Γ,s,b,F,δ), unde

$Q$ este o mulțime finită de stări
$\Gamma$ este alfabetul finit al simbolurilor de pe bandă
$s\in Q$ este starea inițială
$b\in \Gamma$ este simbolul vid
$F\subseteq Q$ este mulțimea stărilor finale (sau acceptante)
$\delta :Q\times \Gamma ^{k}\rightarrow Q\times (\Gamma \times \{L,R,S\})^{k}$ este o funcție parțială numită funcția de tranziție, unde L este deplasarea la stânga, R este deplasarea la dreapta, iar S înseamnă nici o deplasare.

De notat că o mașină Turing cu k benzi nu este mai puternică decât o mașină Turing standard.

Exemplu

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.

 St. Simbol  Simbol      St.
 crt citit   scris  Mișc nouă 
 - - - - - - - - - - - - - - -
  s1  1    ->  0      R   s2
  s2  1    ->  1      R   s2      
  s2  0    ->  0      R   s3
  s3  0    ->  1      L   s4 
  s3  1    ->  1      R   s3
  s4  1    ->  1      L   s4
  s4  0    ->  0      L   s5
  s5  1    ->  1      L   s5
  s5  0    ->  1      R   s1

Seria de calcule pentru această mașină Turing ar fi: (poziția capului e indicată prin simbol îngroșat)

 Pas  Stare Banda  Pas  Stare Banda
 - - - - - - - -   - - - - - - - - -
    1  s1   11        9  s2   1001
    2  s2   01       10  s3   1001
    3  s2   010      11  s3   10010
    4  s3   0100     12  s4   10011
    5  s4   0101     13  s4   10011
    6  s5   0101     14  s5   10011
    7  s5   0101     15  s1   11011
    8  s1   1101       -- halt --

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.

Mașini Turing deterministe și nedeterministe

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).

Mașini Turing universale

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:

Se poate arăta că o singură mașină specială de acest tip poate fi făcută să efectueze lucrul tuturor celorlalte. De fapt ar putea fi făcută să funcționeze ca model al oricărei alte mașini. Mașina specială poate fi numită mașină universală.

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.

Note

^ Hodges, Andrew (2012). Alan Turing: The Enigma (ed. The Centenary). Princeton University Press. ISBN 978-0-691-15564-7.
^ The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by M. H. A. Newman in his lectures: "Was there a definite method, or as Newman put it, a "mechanical process" which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its Proceedings (cf. Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf. Hodges 1983:129).
^ Sipser 2006:137 "A Turing machine can do everything that a real computer can do".

[Hodges-2012-1] Hodges, Andrew (2012). Alan Turing: The Enigma (ed. The Centenary). Princeton University Press. ISBN 978-0-691-15564-7.

[2] The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by M. H. A. Newman in his lectures: "Was there a definite method, or as Newman put it, a "mechanical process" which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its Proceedings (cf. Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf. Hodges 1983:129).

[3] Sipser 2006:137 "A Turing machine can do everything that a real computer can do".

[1]

[2]

[3]