Mașină Turing

În informatică teoretică , o mașină Turing este un model abstract al funcționării dispozitivelor mecanice de calcul , cum ar fi un computer . Acest model a fost conceput de Alan Turing în 1936, pentru a da o definiție precisă conceptului de algoritm sau „procedură mecanică”. Este încă utilizat pe scară largă în informatică teoretică , în special în domeniile complexității algoritmice și a calculabilității .

Inițial, conceptul de mașină Turing, inventat înainte de computer, trebuia să reprezinte o persoană virtuală care efectuează o procedură bine definită, schimbând conținutul casetelor unei panglici infinite, alegând acest conținut dintr-un set finit de simboluri . Pe de altă parte, în fiecare etapă a procedurii, persoana trebuie să se plaseze într-o anumită stare dintr-un set finit de stări. Procedura este formulată în termeni de pași elementari, cum ar fi: "dacă vă aflați în starea 42 și simbolul conținut în celula pe care o priviți este" 0 ", apoi înlocuiți acest simbol cu un" 1 ", mergeți la starea 17 , și acum uită-te la pătratul adiacent din dreapta ”.

În Biserica Teza postulează că orice problemă de calcul bazată pe o procedură algoritmică poate fi rezolvată de către o mașină Turing. Această teză nu este o afirmație matematică, deoarece nu presupune o definiție precisă a procedurilor algoritmice. Pe de altă parte, este posibil să se definească o noțiune de „sistem de programare acceptabil” și să se demonstreze că puterea unor astfel de sisteme este echivalentă cu cea a mașinilor Turing (sunt complete Turing ).

Definiție

Deși numele său de „mașină” poate duce la credința contrară, o mașină Turing este un concept abstract, adică un obiect matematic. O mașină Turing are următoarele componente:

O panglică infinită împărțită în pătrate consecutive. Fiecare casetă conține un simbol al unui alfabet finit dat. Alfabetul conține un simbol special numit „simbol gol” („0” în exemplele care urmează) și unul sau mai multe alte simboluri. Se presupune că banda este infinit de lungă la stânga sau la dreapta, cu alte cuvinte aparatul trebuie să aibă întotdeauna suficientă lungime de bandă pentru a rula. Considerăm că casetele panglicii conțin în mod implicit „simbolul alb”;
Un cap de citire / scriere care poate citi și scrie simboluri pe panglică și se poate deplasa la stânga sau la dreapta panglicii;
Un registru de stat care stochează starea actuală a mașinii Turing. Numărul de stări posibile este întotdeauna finit și există o stare specială numită „stare de pornire”, care este starea inițială a mașinii înainte de executarea acesteia;
Un tabel de acțiuni care indică mașinii ce simbol să scrie pe panglică, cum să mutați capul de redare (de exemplu „ „ pentru o cutie la stânga ”,„ „pentru o cutie la dreapta) și care este starea nouă. , în funcție de simbolul citit pe panglică și de starea curentă a mașinii. Dacă nu există nicio acțiune pentru o combinație dată a unui simbol citit și a unei stări curente, aparatul se oprește. $\ sageata stanga$ $\ sageata dreapta$

Definiție formală

Se pot da mai multe definiții formale apropiate unele de altele ale unei mașini Turing. Una dintre ele, relativ comună, este aleasă aici. O mașină Turing este un quintuplet în care: ${\ displaystyle (Q, \ Gamma, q_ {0}, \ delta, F)}$

$Î$ este un set finit de stări ;
$\Gamma$ este alfabetul de lucru al simbolurilor benzii, care conține un anumit simbol (numit gol ) ; $B$ $B \ in \ Gamma$
$q_0$ este starea inițială , ; $q_ {0} \ în Q$
$\ delta: Q \ times \ Gamma \ to Q \ times \ Gamma \ times \ {\ leftarrow, \ rightarrow \}$ este funcția de tranziție ;
$F$ este setul de stări acceptante (sau finale, terminale) . $F \ subseteq Q$

Este un model al unei mașini Turing complete și deterministe; adică este definit și unic. ${\ displaystyle \ forall q \ in Q, \ forall \ gamma \ in \ Gamma, \ delta (q, \ gamma)}$

Săgețile din definiția lui reprezintă cele două mișcări posibile ale capului de citire / scriere, și anume mișcarea spre stânga și mișcarea spre dreapta. Semnificația acestei funcții de tranziție poate fi explicată în următorul exemplu: înseamnă că dacă mașina Turing se află în stare și citește simbolul , atunci scrie în loc de , merge în stare , apoi își mută capul de joc spre stânga. $\ delta$ $\ delta (q_ {1}, x) = (q_ {2}, y, \ leftarrow)$ $q_ {1}$ $X$ $y$ $X$ $q_ {2}$

Funcționarea mașinii Turing este apoi după cum urmează: la fiecare etapă a calculului său, mașina evoluează în funcție de starea în care se găsește și de simbolul înscris în cutia panglicii unde se află capul de citire. Aceste două informații sunt utilizate pentru a actualiza starea mașinii folosind funcția de tranziție. În momentul inițial, mașina este în stare , iar primul simbol al benzii este intrarea în program. Mașina se oprește când intră într-o stare terminală. Rezultatul calculului este apoi cuvântul format de simbolurile citite succesiv de mașină. $q_0$

Putem constrânge un alfabet al posibilelor intrări din definiție. Este astfel posibil să se lucreze mai precis la acest alfabet rezervând anumite simboluri ale alfabetului complet pentru pașii de calcul ai mașinii. În special, simbolul alb nu trebuie să facă parte din intrare și, prin urmare, poate defini sfârșitul acestuia din urmă . $\ Sigma$ $\Gamma$ $B$

Primul exemplu de mai jos folosește o versiune foarte ușor diferită a unei mașini Turing în care o mașină se oprește dacă este într-o stare terminală și citește un anumit caracter pe panglică (aici simbolul alb). Al doilea exemplu de mai jos este primul exemplu istoric dat de Turing în articolul său din 1936: este o mașină care nu se oprește.

Exemple

Dublați numărul de „1”

Următoarea mașină Turing are un alfabet {'0', '1'}, „0” fiind „simbolul alb”. Să presupunem că panglica conține o serie de „1”, iar capul de citire / scriere este inițial deasupra „1” din partea stângă. Această mașină are ca efect dublarea numărului de „1”, prin inserarea unui „0” între cele două serii. De exemplu, „111” devine „1110111”.
Setul de stări posibile ale mașinii este {e1, e2, e3, e4, e5}, iar starea inițială este e1.
Tabelul de acțiuni este după cum urmează:

Exemplu de tabel de tranziție

Stare veche	Citiți simbolul	Simbol scris	Circulaţie	Stare nouă
e1	0	(Stop)
e1	1	0	Dreapta	e2
e2	1	1	Dreapta	e2
e2	0	0	Dreapta	e3
e3	1	1	Dreapta	e3
e3	0	1	Stânga	e4
e4	1	1	Stânga	e4
e4	0	0	Stânga	e5
e5	1	1	Stânga	e5
e5	0	1	Dreapta	e1

Rularea acestei mașini pentru o serie de două 1 ar fi (poziția capului de citire / scriere pe bandă este scrisă cu litere aldine și roșii):

Execuție (1)

Etapă	Stat	Panglică
1	e1	1 1
2	e2	0 1
3	e2	01 0
4	e3	010 0

Execuție (2)

Etapă	Stat	Panglică
5	e4	01 0 1
6	e5	0 1 01
7	e5	0 101
8	e1	1 1 01

Execuție (3)

Etapă	Stat	Panglică
9	e2	10 0 1
10	e3	100 1
11	e3	1001 0
12	e4	100 1 1

Execuție (4)

Etapă	Stat	Panglică
13	e4	10 0 11
14	e5	1 0 011
15	e1	11 0 11
	(Stop)

Comportamentul acestei mașini poate fi descris ca o buclă:

Își începe execuția în starea e1, înlocuiește primul 1 cu un 0.
Apoi folosește starea e2 pentru a se deplasa la dreapta, sărind peste 1 (doar unul în acest exemplu) până când întâlnește un 0 (sau un gol) și intră în starea e3.
Starea e3 este apoi utilizată pentru a sări următoarea secvență de 1 (inițial niciuna) și pentru a înlocui primul 0 întâlnit cu un 1.
Starea e4 face posibilă revenirea la stânga până când se găsește un 0 și trecerea la starea e5.
Starea e5 face posibilă din nou deplasarea spre stânga până când se găsește un 0, scris inițial de starea e1.
Aparatul înlocuiește apoi acest 0 cu un 1, mută o celulă spre dreapta și trece din nou la starea e1 pentru o nouă iterație a buclei.

Acest proces se repetă până când e1 cade pe un 0 (este mijlocul 0 între cele două secvențe ale lui 1); în acest moment, mașina se oprește.

Calculați o treime în binar

În exemplul următor, mașina Turing are o panglică goală și vă permite să construiți secvența 01010101010101 ...

Exemplu de tabel infinit

Stare veche	Simbol scris	Circulaţie	Stare nouă
La	0	Dreapta	b
b	1	Dreapta	La

Execuția acestei mașini ar fi (poziția capului de citire / scriere pe bandă este scrisă cu caractere aldine și magenta ):

Rularea Mașinii Infinite

Etapă	Stat	Panglică
1	La	0
2	b	0 1
3	La	01 0
4	b	010 1
5	La	0101 0
6	b	01010 1
7	La	010101 0
8	b	0101010 1
...	...	01010101 ...

Comportamentul acestei mașini poate fi descris ca o buclă infinită:

Își începe execuția în starea a, adaugă un 0 și se deplasează spre dreapta.
Apoi trece la starea b, adaugă un 1 și se deplasează spre dreapta.
Revine la starea a și repetă primul pas.

Această mașină este contrapartida calculului unei treimi a cărei scriere în binar este 0,010101010101 ...

Mașini universale Turing

După cum arată Alan Turing în articolul său seminal, este posibil să se creeze o mașină Turing numită „mașină universală Turing” care este capabilă să „simule” comportamentul oricărei alte mașini Turing. „Simulați” înseamnă că, dacă mașina universală Turing primește ca intrare o codificare a unei mașini T și a datelor D , produce același rezultat ca mașina T căreia i se vor da datele D ca intrare .

O mașină universală Turing are capacitatea de a calcula orice este calculabil: spunem apoi că este complet Turing . Furnizându-i codificarea adecvată, poate simula orice funcție recursivă , analiza orice limbaj recursiv și poate accepta orice limbaj parțial decis . Conform tezei Church-Turing , problemele care pot fi rezolvate de o mașină universală Turing sunt exact problemele care pot fi rezolvate printr-un algoritm sau printr-o metodă concretă de calcul .

Realizarea unei mașini Turing

O mașină Turing este un obiect de gândire: panglica ei este infinită și, prin urmare, memoria unei mașini Turing este infinită. O mașină Turing nu generează niciodată depășirea memoriei , spre deosebire de un computer a cărui memorie este finită. Uitând această problemă de memorie, putem simula o mașină Turing pe un computer modern.

De asemenea, este posibil să se construiască mașini Turing pur mecanice. Mașina Turing, obiect de gândire, a fost astfel reificată în numeroase ocazii folosind tehnici uneori destul de originale, dintre care iată câteva exemple:

În aprilie 2011, Jim MacArthur a realizat o mașină Turing mecanică compactă cu 5 simboluri, cu rulmenți cu bile, ca suport de informații pe panglică.
În martie 2012, cu ocazia anului Turing (ro) , o echipă de studenți de la École normale supérieure de Lyon a produs o mașină Turing realizată în întregime din piese Lego fără electronică.

În Decembrie 2013, un prototip experimental pentru a face mașinile Turing o realitate, (electromecanică: realizată cu tehnologii din epoca Turing), cu o panglică circulară și relativ ușor de programat. Proiectat în două părți transportabile, poate fi folosit pentru prezentări și lecții.
În octombrie 2020, un aparat educațional Turing proiectat de Thierry Delattre (Dunkerque), programabil pentru algoritmi cu maximum 12 stări și cu un alfabet de 3 simboluri. 50 de algoritmi pot fi stocați în memorie. O versiune cu 22 de state și 8 simboluri datează din februarie 2021.

Referințe și bibliografie

Referințe

(în) Harry R. Lewis și Christos Papadimitriou , Elements of theory of computation . Prentice-Hall , 1982; a doua ediție septembrie 1997.
„FINAL“ , CNRTL: „De fapt, există plutind între finale și finale : a 1 st pare a fi formulate la plural. de lang. curte. și scriitori, al doilea cel al lingviștilor și economiștilor ” .
Kévin Perrot, „ Calculabilitate. Cursul 1: Mașini Turing ” , pe univ-mrs.fr ,primavara 2019(consultat în noiembrie 2020 )
(în) Jim MacArthur, „ Turing Machine ” , pe srimech.blogspot.fr ,8 iunie 2012(accesat la 20 februarie 2018 ) .
„ Proiectul RUBENS ” , pe rubens.ens-lyon.fr ,martie 2012(accesat la 20 februarie 2018 ) .
David Larousserie, Le Monde , „ O mașină complet mecanică căreia nu îi lipsește aerul ” , pe lemonde.fr ,22 iunie 2012(accesat la 20 februarie 2018 ) .
Marc Raynaud, „ Un prototip programabil pentru realizarea mașinii Turing ” , pe machinedeturing.org (accesat la 19 februarie 2018 ) .
Ouest-France , „ Marc Raynaud, un invatat matematician învățat ” , pe ouest-france.fr ,14 februarie 2018(accesat la 14 septembrie 2020 ) .
„ Turing Machine - Code are apoi animații ușoare captivante, calcule matematice pe numere binare, serii de numere sau orice altă aplicație pe care o poți inventa în timpul tău liber!” » (Accesat pe 19 martie 2021 )

Bibliografie

Manuale

Olivier Carton, Limbaje formale, calculabilitate și complexitate: licență și master în matematică sau informatică, opțiunea informatică a agregării matematicii , Paris, Vuibert ,2008, 237 p. ( ISBN 978-2-7117-2077-4 , SUDOC 128299258 ) ;
Jean-Michel Autebert, Computabilitate și decidabilitate , Paris, Masson,1992, 118 p. ( ISBN 978-2-225-82632-0 , SUDOC 002676494 ) ;
Éric Jacopin, Les machines de Turing: Introducere în caracterizarea complexității unei probleme , Toulouse, Éditions Cépaduès ,2009, 264 p. ( ISBN 978-2-85428-865-0 , SUDOC 132323214 ) ;

Turing

Alan Turing și Jean-Yves Girard , La machine de Turing , Paris, Éditions du Seuil,1995, 192 p. [ detaliu ediție ] ( ISBN 9782020369282 ) ; această lucrare include în special o traducere în franceză (de Julien Basch și Patrice Blanchard) a articolului original, precum și o corecție de către Emil Post a erorilor care apar acolo;
(ro) Alan Turing, „ On Computable Numbers, with an Application to the Entscheidungsproblem ”, Proceedings of the London Mathematical Society, Seria 2 , vol. 45,1936, p. 230-265 ( citește online ) ;
(fr) Alan Turing, Precizia din „Numere calculabile” ( citește online ). - O schiță pentru o notă pentru redarea Academiei de Științe din Paris.

Kleene

Stephen Cole Kleene , Introducere în metamatematică , Amsterdam, Olanda de Nord,1952, x + 550 p. ( SUDOC 005505526 , prezentare online ) - Numeroase reeditări, în 1957, 1959, 1962, 1964, 1967, 1971, 1974, 1980, 1988, 1991, 1996, 2000, 2009, în special de Wolters-Noordhoff (Groningen) ( ISBN 0720421039 ) , conform notificării Sudoc. Multe traduceri.
(en) , (fr) Stephen Cole Kleene, Mathematical Logic , Dover ,1967- Reimprimare reeditare Dover, 2001, ( ISBN 0-486-42533-9 ) . Traducere franceză de Jean Largeault , Logique mathématique , Armand Colin, 1971 și Gabay 1987 ( ISBN 2-87647-005-5 ) .

: document utilizat ca sursă pentru acest articol.

Vezi și tu

Articole similare

Mașină de Turing nedeterministă ;
Mașină probabilistică de Turing ;
Mașină alternativă Turing ;
Mașină Turing simetrică ;
Mașină Blum-Shub-Smale : o generalizare a mașinilor care calculează ; $\ mathbb {R}$
Problema deciziei ;
Experiment de gândire ;
Oracle (mașină Turing) ;
Imitation Game , film despre viața lui Alan Turing alături de Benedict Cumberbatch ;
Funcție construibilă .

linkuri externe

Filmul „Mașina de Turing realizată” de Christophe Gombert și Hugo Deboise de vizionat online gratuit.
Geniul întrerupt al lui Alan Turing : prezentare și bibliografie a unei conferințe BnF de Bernard Chazelle , programată pentru19 martie 2014
Hamdi Ben Abdallah, „ Cum funcționează o mașină Turing? », Interstiții ,22 martie 2013( citește online ), articol care permite încercarea unei mașini Turing.