Mașină Turing

Un exemplu de mașină Turing

În informatică, o mașină Turing (sau MdT pe scurt) este o mașină ideală care manipulează datele conținute pe o bandă cu lungime potențial infinită, conform unui set predeterminat de reguli bine definite. Cu alte cuvinte, este un model abstract care definește o mașină capabilă să execute algoritmi și echipată cu o bandă potențial infinită pe care poate citi și / sau scrie simboluri.

Introdus în 1936 de Alan Turing ca model de calcul pentru a răspunde la problema Entscheidungs (problema de decizie) propusă de Hilbert în programul său de fundamentare formalist pentru matematică , este un instrument teoretic puternic care este utilizat pe scară largă în teoria calculabilității și în studiul complexității algoritmilor. , deoarece este de un ajutor considerabil pentru cercetători în înțelegerea limitelor calculului mecanic; importanța sa este de așa natură încât astăzi, pentru a defini noțiunea de algoritm într-un mod formal precis , tindem să o readucem la calculele care pot fi efectuate cu mașinile Turing.

Descriere

Are particularitatea de a fi guvernat de reguli de o natură foarte simplă, adică poate fi descris ca fiind format din mecanisme elementare foarte simple; în plus, este posibil să-și prezinte evoluțiile la un nivel sintetic prin descrieri mecanice destul de intuitive. Pe de altă parte, are calculabilitatea care se presupune a fi maximă: se arată, de fapt, că este capabil să efectueze toate calculele care pot fi efectuate de celelalte modele de calcul cunoscute de om. Printre aceste modele computaționale ne amintim de funcțiile recursive ale lui Jacques Herbrand și Kurt Gödel , calculul lambda al bisericii Alonzo și Stephen Kleene , logica combinatorie a lui Moses Schönfinkel și Haskell Curry , algoritmii Markov , sistemele lui Thue , sistemele Post , Mașinile lui Hao Wang și RAM- ul abstract al lui Marvin Minsky sau mașinile cu registre elementare . În consecință, s-a consolidat convingerea că pentru fiecare problemă calculabilă există un MdT capabil să o rezolve: aceasta este așa-numita conjectură Church-Turing , care postulează în esență că pentru fiecare funcție calculabilă există o mașină Turing echivalentă, adică „setul de funcții calculabile coincide cu cel al funcțiilor recursive.

Algoritmii care pot fi implementați de un MdT se numesc „algoritmi calculabili Turing”.

Caracteristici

În 1936 a fost publicat un articol de Alan Mathison Turing intitulat Despre numere calculabile, cu o aplicație la Entscheidungsproblem , în care autorul a rezolvat negativ problema Entscheidungsproblem sau problema de decizie lansată în 1900 de David Hilbert și Wilhelm Ackermann .

Întrebarea fusese pusă de Hilbert în următorii termeni: „Există întotdeauna, cel puțin în principiu, o metodă mecanică (adică un mod riguros) prin care, având în vedere orice afirmație matematică, este posibil să se stabilească dacă este adevărat sau fals? "

Avantajele de a avea o astfel de metodă sunt enorme și merită tot accentul pe care Hilbert și mulți alții care l-au urmat l-au pus întrebării: un astfel de algoritm ar putea rezolva toate problemele matematice și, mult mai mult, ar fi posibil să se reducă orice om raționament prin simplul calcul mecanizabil. Un prim răspuns puternic a fost dat de matematicianul boem Gödel cu ocazia celei de-a doua conferințe despre epistemologia științelor exacte din Königsberg (1930), în care a exprimat pentru prima dată public ideile conținute în cea mai faimoasă lucrare a sa despre incompletitudinea sistemelor formale coerente ( prima teoremă a incompletitudinii ); Gödel a arătat că simpla coerență a unui sistem formal nu poate garanta că ceea ce este dovedit în el este adevărat sau fals. Visul lui Hilbert se estompase deja în momentul în care Turing și-a publicat articolul, în care a demonstrat insolubilitatea problemei Entscheidungs.

"Un tânăr străin pe nume Alan Turing a rezolvat întrebarea aproape ca pe o glumă. Cu un aparat imaginar." ^[1] .

Soluția propusă de Turing constă în utilizarea unui model matematic capabil să simuleze procesul de calcul uman, descompunându-l în etapele sale finale.
Mașina constă dintr-un cap de citire și scriere cu care este capabil să citească și să scrie pe o bandă potențial infinită partiționată, într-un mod discret, în cutii. La fiecare moment al timpului t ₁ , mașina se află într-o stare internă bine determinată s ₁ , rezultatul procesării efectuate pe datele citite.

Starea internă sau configurația unui sistem este condiția în care componentele mașinii se găsesc la un moment dat de timp t . Componentele de luat în considerare sunt:

numărul celulei observate
conținutul său
instrucțiunea de executare

Dintre toate stările posibile, se disting următoarele:

o configurație inițială , pentru t = t ₀ (înainte de executarea programului)
o configurație finală , pentru t = t _n (la sfârșitul execuției programului)
a configurațiilor intermediare , pentru t = t _i (înainte de executarea instrucțiunii o _i )

Implementarea unui algoritm în acest context înseamnă efectuarea uneia dintre cele patru operații elementare

mutați o cutie spre dreapta
mutați o cutie la stânga
scrie un simbol preluat dintr-un set de simboluri de care dispune pe o cutie
ștergeți un simbol deja scris pe pătratul pe care îl observă
sau opriți-vă

Executarea unei operații o ₁ , între momentele de timp t ₁ și t ₂ , înseamnă trecerea de la starea internă s ₁ la s ₂ . Mai formal, acest lucru este exprimat în simboluri precum: {s ₁ , a ₁ , sau ₁ , s ₂ } pentru a fi citit ca: în starea internă s ₁ aparatul observă simbolul a ₁ , efectuează operația o ₁ și găsește ea însăși în statul intern s ₂ .
Turing a reușit să demonstreze că un astfel de instrument, cu caracteristici atât de definite rigid, este capabil să efectueze orice calcul, dar nu s-a oprit aici; el a înțeles că calculabilitatea era o rudă apropiată a probabilității și, prin urmare, la fel cum Gödel distrusese visele de glorie ale lui Principia Mathematica a lui Russell și Whitehead , tot așa mașinile sale puteau închide definitiv problema Entscheidungsproblem .

Definiție

Sunt luate în considerare multe variante ( modele ) ale MdT, care se dovedesc a avea același domeniu. Aici pornim de la o variantă destul de simplă pe care o putem numi o mașină Turing deterministă cu o singură bandă, cu instrucțiuni în cinci câmpuri . Alte variante sunt prezentate mai jos.

Introducere informală

Mașina poate funcționa pe o bandă care apare ca o secvență de cutii în care pot fi înregistrate simbolurile unui alfabet bine determinat; este echipat cu un cap de citire și scriere (I / O) cu care este capabil să efectueze operații de citire și scriere pe o casetă de bandă. Mașina evoluează în timp și în orice moment se poate găsi într-o stare internă bine determinată , care face parte dintr-un set finit de stări. Inițial, pe bandă este plasat un șir care reprezintă datele care caracterizează problema care este trimisă mașinii. Mașina este, de asemenea, echipată cu un repertoriu finit de instrucțiuni care determină evoluția sa ca o consecință a datelor inițiale. Evoluția se dezvoltă prin pași succesivi care corespund unei secvențe discrete de instanțe succesive. Proprietățile anterioare sunt comune multor mașini formale ( automat cu stare finită , automat de stivă , ...). O caracteristică a MdT este aceea de a avea o centură potențial infinită, adică poate fi extinsă cât de mult doriți dacă acest lucru devine necesar.

Fiecare pas evoluție este determinată de starea actuală s în care se află mașina și de caracterul c că I / O descoperiri ale capului de pe caseta bandă pe care este poziționat și ia forma oricărei modificări a conținutului cutiei , în „posibila mișcare a capului unei poziții spre dreapta sau spre stânga și în eventuala schimbare a stării. Ce acțiuni sunt efectuate la fiecare etapă este determinată de instrucțiunea pe care o presupunem că este unică, care are ca primele două componente s și c ; celelalte trei componente ale declarației furnizează noua stare, noul caracter și o cerere de mutare la stânga, nulă sau dreaptă în ordine.

O evoluție a mașinii constă dintr-o succesiune de „configurații” posibile ale acesteia, fiecare configurație constând din starea internă curentă, conținutul benzii (un șir de lungime finită) și poziția pe banda capului I / O. În cele mai simple cazuri, evoluția se oprește la un moment dat, deoarece nu există nicio instrucțiune care să o facă să continue. Puteți avea un blocaj într-o configurație „utilă” din punctul de vedere al problemei pe care doriți să o rezolvați; în acest caz, ceea ce este înregistrat pe bandă în momentul arestării reprezintă rezultatul procesării. Cu toate acestea, poate exista și o oprire „inutilă” care trebuie considerată o concluzie eronată a procesării. Trebuie spus imediat că se poate întâmpla, de asemenea, ca o evoluție să nu se sfârșească niciodată (vezi secțiunea următoare și problema de oprire ).

Setare formală

Definim o mașină Turing deterministică cu o singură bandă și instrucțiuni cu cinci câmpuri , termen pe care îl abreviatem ca MdT1n5i, o mașină formală de următoarea formă:

T=\langle S,s_{0},F,A,\beta ,\delta \rangle \quad {\mbox{dove}}

{\ displaystyle T = \ langle S, s_ {0}, F, A, \ beta, \ delta \ rangle \ quad {\ mbox {where}}}

T = \ langle S, s_ {0}, F, A, \ beta, \ delta \ rangle \ quad {\ mbox {where}}

$S.$ ${\ displaystyle S}$ $S.$ este un set finit numit set de stări ale mașinii;

$s_{0}$ ${\ displaystyle s_ {0}}$ $s_ {0}$ este un element al lui S numit starea inițială a lui T ;

$F.$ ${\ displaystyle F}$ $F.$ este un subset al lui S numit ansamblul stărilor finale ale lui T ;

$LA$ ${\ displaystyle A}$ $LA$ este un alfabet finit numit alfabet panglică T.

$\beta$ ${\ displaystyle \ beta}$ $\ beta$ este un caracter al alfabetului A numit semnul celulei goale a benzii T.

$\delta ~:~S\times A\to S\times A\times \{-1,0,+1\}$ ${\ displaystyle \ delta ~: ~ S \ times A \ to S \ times A \ times \ {- 1,0, + 1 \}}$ $\ delta ~: ~ S \ times A \ to S \ times A \ times \ {- 1,0, + 1 \}$ se numește funcția de tranziție a mașinii.

De sine $\delta (s,a)=\langle t,b,m\rangle$ ${\ displaystyle \ delta (s, a) = \ langle t, b, m \ rangle}$ $\ delta (s, a) = \ langle t, b, m \ rangle$ , cvintuplul corespunzător $\langle s,a,t,b,m\rangle$ ${\ displaystyle \ langle s, a, t, b, m \ rangle}$ $\ langle s, a, t, b, m \ rangle$ poate fi considerat ca instrucțiunea care se execută atunci când mașina este în starea s și capul I / O citește a pe cutia pe care este poziționat; implică trecerea la starea t , scrierea caracterului b și:

când m = -1 mișcarea capului o poziție spre stânga,
când m = 0 fără mișcare a capului,
când m = +1 mișcarea capului o poziție spre dreapta.

Extinderea domeniului de aplicare și conjectura Bisericii-Turing

Același subiect în detaliu: conjectura Bisericii-Turing .

Importanța MdT derivă din faptul că permite realizarea tuturor elaborărilor efectuate de mașinile (electronice sau mecanice) care au apărut în istoria umanității, inclusiv elaborările care sunt efectuate astăzi cu cele mai avansate tehnologii și computerele de astăzi și chiar dovezile matematice pe care umanitatea le-a adunat de-a lungul istoriei sale.

De fapt, toate mașinile cunoscute pot fi urmărite până la modelul Turing extrem de simplu. De exemplu, chiar și cele mai complexe computere din prezent pot fi urmărite la acest model:

În primul rând, sunt identificate mașini relativ simple care efectuează operațiuni aritmetice de bază și scheme de compoziție ale acestor mașini care permit calcularea tuturor funcțiilor care au ca intrare numerele naturale. Aceste funcții corespund expresiilor obținute prin combinarea operațiilor de mai sus, după dorință.
Prin urmare, sunt identificate versiuni ale MdT mai bogate în resurse, care fac posibilă descrierea mai ușoară a operațiilor din ce în ce mai complexe și care privesc entități discrete de cele mai variate tipuri (numere raționale, grafice, șiruri, expresii simbolice de diferite tipuri,. ..), dar toate referibile la numere naturale; elaborările și entitățile de cele mai variate tipuri trebuie luate în considerare pentru a susține conjectura Biserică-Turing.
Continuând în această direcție, sunt introduse MdT-uri echipate cu memorii complexe, cum ar fi secvențe de benzi și amintiri bidimensionale și tridimensionale, similare cu discurile și teancurile de discuri; mașini care au capacitatea de a organiza instrucțiuni într-un mod similar cu apelarea unui subrutină, așa cum este cerut de limbajele de programare utilizate.
Alte îmbogățiri pot include calcule simbolice și prelucrări paralele.
În acest moment trebuie adăugat, de asemenea, că este adecvat să se ia în considerare variante nedeterministe ale TM, mașini formale care sunt capabile să efectueze diverse elaborări simultan, într-un număr nelimitat. Aceste mașini formale, la prima vedere departe de modelele de mecanisme concret realizabile, pot fi considerate idealizări ale sistemelor informatice care funcționează în paralel, sisteme pe care tehnologia actuală le permite să realizeze destul de frecvent (așa-numitele clustere ).

Cu acest raționament, se obțin mașini formale care, în principiu, pot fi urmărite până la MdT introdus inițial, dar care pot fi programate mult mai ușor și mai ales care pot fi realizate cu tehnologiile disponibile astăzi. A demonstra că una dintre aceste mașini poate rezolva o anumită problemă înseamnă a demonstra că și TM o poate rezolva. Concluzia este că toate calculele care pot fi efectuate de mașini cunoscute de noi pot fi efectuate și de MdT.

O mașină care vă permite să rezolvați toate problemele care pot fi rezolvate și de MdT se numește „echivalent Turing”. Concluzia este că toate calculele care pot fi efectuate de MdT pot fi efectuate și de toate mașinile a căror echivalență cu MdT poate fi demonstrată.

Prin urmare, importanța MdT este dublă: nu numai că este cel mai „puternic” model de mașină teoretică cunoscut, dar poate fi folosit și pentru a testa puterea noilor modele teoretice. De asemenea, este posibil să se demonstreze echivalența cu MdT folosind un model mai simplu, care este deja cunoscut ca fiind echivalent cu Turing. Aceasta permite ca rezultatele teoretice obținute pentru alte modele de mașini să fie reutilizate cu ușurință pentru un anumit model de mașină.
Mai mult, MdT și alte modele pot fi utilizate pentru a demonstra capacitățile de calcul ale limbajelor de programare (așa cum sunt demonstrate capacitățile mașinilor abstracte respective).

Toate aceste considerații fac rezonabil să susțină conjectura Biserică-Turing . Cu toate acestea, acestea se referă la calculabilitatea algoritmilor și nu la tractabilitatea lor: mașinile echivalente sunt fabricate diferit și, prin urmare, pot efectua același calcul cu un număr diferit de pași sau risipă de resurse (memorie, timp și altele). De exemplu, un calcul pe care computerul de astăzi îl efectuează în câteva secunde ar necesita un număr enorm de pași dacă se efectuează pe un mecanism echipat cu dispozitive de operare extrem de simple, cum ar fi cele ale TM. Pe scurt, diferite mașini pot rezolva aceleași probleme cu programe care au complexitate de calcul diferită.

Problema arestării și indecidabilitatea acesteia

În unele circumstanțe, poate fi util să se ia în considerare un TM care are o evoluție nelimitată (de fapt, resursele de spațiu și timp disponibile pentru mașină sunt considerate a fi infinite). De exemplu, este interesant să faci un MdT care să genereze elementele unei succesiuni de obiecte (de exemplu numerele prime succesive sau numerele Mersenne succesive sau cifrele zecimale ulterioare ale unui număr) să procedeze „nelimitat” (adică „ce este util”) irațional ca pi ). În alte cazuri, însă, o evoluție nelimitată a unei TM este considerată un eșec. Când doriți ca un TM să caute un element cu anumite caracteristici într-un set numărabil și continuă cu căutarea fără să ofere nicio indicație, vă aflați într-o situație decisiv nesatisfăcătoare: nu știți dacă să întrerupeți o procesare inutilă sau să așteptați o rezultatul că ar putea fi furnizat după lucrări ulterioare într-un interval de timp acceptabil.

Prin urmare, este important să putem stabili dacă un MdT sau un alt sistem formal echivalent („calculul lambda” al Bisericii, de exemplu), atunci când un șir (de date) i se prezintă, se oprește sau nu. Aceasta se numește problema opririi sau problema opririi mașinii Turing. Există cazuri în care se demonstrează sau se verifică existența unei arestări, cazuri pentru care se arată că evoluția nu se oprește, dar ar putea continua la nesfârșit și cazuri pentru care nu se cunoaște un răspuns.

Pare rezonabil să se caute o procedură generală pentru a decide una dintre aceste probleme. Având în vedere că MdT-urile se dovedesc a fi capabile să rezolve toate problemele care pot fi rezolvate cu celelalte proceduri cunoscute, este logic să ne întrebăm dacă există o mașină Turing capabilă să decidă pentru orice pereche (M, d) constituită de un MdT M și dintr-un șir de date d dacă, atunci când este furnizat de la M, acesta evoluează până când se oprește sau nu. Această cerere este făcută și mai semnificativă prin existența, demonstrată de Turing însuși, a unei așa-numite mașini universale Turing , o mașină capabilă să simuleze orice evoluție a oricărui MdT (chiar și propriile evoluții!). Ei bine, Turing a arătat că mașina universală Turing nu este capabilă să decidă problema arestării în fiecare caz. Deci, nici o mașină Turing nu poate face asta. Acest rezultat negativ este exprimat spunând că problema arestării este de Turing-indecidabilă . Dacă acceptăm supoziția Biserică-Turing asupra scopului mașinii Turing, concluzionăm că problema opririi mașinii Turing este indecidabilă.

Acest rezultat negativ constituie o limită pentru toate mecanismele de calcul; constituie un rezultat limitativ de mare importanță generală și pentru studiul algoritmilor. Importanța generală depinde de faptul că fiecare procedură de demonstrație automată este echivalentă cu un calcul care poate fi efectuat cu o mașină Turing. Trebuie subliniat faptul că indecidibilitatea Turing a problemei de oprire se dovedește a fi echivalentă cu teorema incompletitudinii lui Gödel , primul rezultat limitativ fundamental pentru matematică. De asemenea, în studiul algoritmilor și al complexității acestora se constată că multe alte rezultate limitative pot fi deduse destul de ușor din indecidabilitatea arestului.

Istorie

Mașină de calcul

Modelul unei părți a motorului analitic al lui Babbage expus la London Science Museum ^[2] .

Noțiunea de „mașină de calcul” are o origine anterioară lucrărilor lui Turing, Robin Gandy (1919-1995) - student al lui Alan Turing (1912-1954) și ulterior un prieten de-a lungul vieții ^[3] - a trasat descendența până la începutul lui Charles Babbage (1834).

Iată cum descrie „ Teoria lui Babbage ”: Că întreaga dezvoltare și operațiuni de analiză sunt acum capabile să fie executate de mașini . ^[4] (Astfel, întregul mod de a dezvolta și de a efectua operațiuni de analiză poate fi realizat de o singură mașină.)

Analiza lui Gandy a motorului analitic al lui Babbage derivă următoarele operații ^[5] :

Funcțiile aritmetice +, -, ×, unde - indică scăderea „corectă”: x - y = 0 dacă y ≥ x.
Orice secvență de operații este o operație.
Iterarea unei operații (repetarea de n ori a unei operații P).
Iterație condiționată (repetarea de n ori a unei operații P condiționată de „succesul” testului T).
Transfer condiționat (adică condițional „treceți”). ^[6]

sau

Funcțiile aritmetice +, -, ×, unde - denotă scăderea „în sensul propriu”: x - y = 0 dacă y ≥ x.
Orice secvență de operații este o operație.
Iterația unei operații (repetați operația P de un anumit număr de ori).
Iterația condiționată (repetați de mai multe ori o operație P condiționată de „succesul” testului T).
Transferul condiționat (adică condițional „ merge ”).

Gandy susține că „funcțiile care pot fi calculate din (1), (2) și (4) sunt tocmai cele calculate de Turing”. ^[5] .

El citează și alte „mașini de calcul universale”, inclusiv cele ale lui Percy Ludgate (1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken ( 1937).

Constanta fundamentală este programarea unui număr fix de secvențe de operații aritmetice (chiar dacă caracteristicile importante ale interacțiunii condiționate și ale transferului condițional pentru teoria de calcul a unei mașini nu sunt recunoscute universal). ^[6]

Problema deciziei (Entscheidungsproblem): a zecea întrebare a lui Hilbert

Deși valoarea întrebărilor puse de celebrul matematician David Hilbert în 1900 este de necontestat, trebuie considerat că un aspect al zecelea dintre problemele pe care le-a pus a derivat timp de cel puțin treizeci de ani fără a fi stabilit într-o manieră precisă.

Urmează formularea originală a lui Hilbert pentru a zecea problemă:

10. Determinarea solvabilității unei ecuații diofantine . Având în vedere o ecuație diofantină cu orice număr de mărimi necunoscute și cu coeficienți integrali raționali: Pentru a concepe un proces conform căruia se poate determina într-un număr finit de operații dacă ecuația este rezolvabilă în numere întregi raționale. Problema Entscheidungs [problema de decizie pentru logica de prim ordin] este rezolvată atunci când cunoaștem o procedură care permite oricărei expresii logice date să decidă prin numeroase operații validitatea sau satisfacția sa ... Problema Entscheidungs trebuie considerată principala problemă a logicii matematice. ^[7] (10. Determinarea solvabilității unei ecuații diofantine . Având în vedere o ecuație diofantină în orice număr de necunoscute și cu coeficienți întregi raționali: elaborați o procedură prin care este posibil să stabiliți, într-un număr finit de operații, dacă ecuația este rezolvabilă în numere întregi raționale. Problema Entscheidungs (problema de decizie pentru logica de ordinul întâi) este rezolvată atunci când ajungem la o procedură care ne permite să decidem printr-un număr finit de expresii validitatea sau satisfacția pentru orice expresie logică dată. (... ) Problema Entscheidungs trebuie considerată principala problemă a logicii matematice (...)).

Încă din 1922, această noțiune de problemă Entscheidung a fost dezvoltată de H. Behmann :

(...) cea mai generală formă a Entscheidungsproblem [este] după cum urmează: este necesară o prescripție generală destul de definită, care să permită să se decidă într-un număr finit de pași adevărul sau falsitatea unei afirmații pur logice date ... Behmann remarcă faptul că ... problema generală este echivalentă cu problema de a decide ce propoziții matematice sunt adevărate. Dacă s-ar putea rezolva problema Entscheidungs, atunci ar avea o „procedură pentru rezolvarea multor (sau chiar a tuturor) problemelor matematice”. ^[8]
((...) urmează formula mai generală a problemei Entscheidungs: este necesară o prescripție suficient de definită, în general aplicabilă, pentru a ne permite să decidem într-un număr finit de pasaje adevărul sau falsitatea unei afirmații date pur logice. Behmann observă: ( (...) ...) problema generală coincide cu problema de a decide ce propoziții matematice sunt adevărate. (...) Dacă cineva ar putea rezolva problema Entscheidungs, atunci el ar avea o „procedură pentru a rezolva cel mai mult (sau chiar toate) problemele matematice ").

În 1928, la Congresul internațional al matematicienilor , Hilbert însuși "și-a formulat întrebarea destul de precis. În primul rând, dacă matematica este completă, (...) în al doilea rând dacă este consecventă, (...) în al treilea rând dacă este decisă" (Hodges ^{[ 9]} ). Kurt Gödel a răspuns primelor două întrebări în 1930 (la aceeași conferință în care Hilbert a ținut discursul de adio); al treilea - problema Entscheidungs - a trebuit să aștepte până la mijlocul anilor 1930. Problema a fost că un răspuns a necesitat o definiție precisă a „ prescripției definite în general aplicabile ” sau, așa cum o va numi profesorul Alonzo Church din Princeton, „calculabilitate eficientă”, iar în 1928 nu a existat niciuna.

Cu toate acestea, în anii următori, Emil Post a dezvoltat o definiție pentru „un lucrător capabil să se deplaseze între diferite locații, scriind și ștergând semne în conformitate cu o listă de instrucțiuni” (1936), la fel și Church și unii dintre studenții săi ( Stephen Kleene și JB Rosser ) .cu calcul lambda și teoria lui Gödel a funcțiilor recursive primitive (1934). Raportul Bisericii (publicat în aprilie 1936) a rezolvat problema Entscheidungs arătând indecidabilitatea ei, depășind timpul Turing (a cărui teorie a fost formulată în mai 1936, dar publicată abia în 1937). (Între timp, Post a lucrat și la tema, totuși, plasându-se în toamna anului 1936, apoi ulterior în Turing). Cu toate acestea, opera lui Turing diferă semnificativ de lucrările Church and Post, fiind caracterizată prin construirea directă a unui argument care a plecat de la principiile fondatoare ale întrebării (Hodges ^[10] ).

Mașina lui Alan Turing

În primăvara anului 1935, Turing, ca tânăr student de masterat la King's College, Cambridge , a acceptat provocarea. Fusese stimulat de lecțiile logicianului Max Newman, care l-a prezentat la opera lui Gödel și la problema Entscheidungs (problema de oprire) ^[11] , ultimele frontiere ale cunoașterii matematice. Newman a pus întrebarea asupra conceptului de „proces mecanic” ca mijloc de analiză a problemei lui Hilbert, o alegere puternic criticată de comunitatea matematică engleză. În necrologul lui Turing din 1955, Newman scrie:

La întrebarea „ce este un proces„ mecanic ”? ' Turing a returnat răspunsul caracteristic „Ceva ce poate fi făcut de o mașină” și s-a angajat în sarcina extrem de congenială de a analiza noțiunea generală de mașină de calcul.
—Gandy p. 74 ^[12]
La întrebarea „ce este un proces mecanic?” Turing a returnat răspunsul caracteristic „Ceva ce poate fi făcut de o mașină” și s-a angajat în sarcina extrem de congenială de a analiza noțiunea generală a unei mașini computerizate.

Gandy scrie:

Presupun, dar nu știu, că Turing, chiar de la începutul lucrării sale, a avut drept scop o dovadă a indecizibilității problemei Entscheidungs. He told me that the 'main idea' of the paper came to him when he was lying in Grantchester meadows in the summer of 1935. The 'main idea' might have either been his analysis of computation or his realization that there was a universal machine, and so a diagonal argument to prove unsolvability (...)
— ibid., p. 76 ^[13]
Suppongo, ma non lo so, che Turing, fin dall'inizio del suo lavoro, avesse come obiettivo quello di provare l'indecidibilità dell'Entscheidungsproblem. Mi disse che l'idea principale del documento gli venne in mente quando giaceva nei prati di Grantchester, nell'estate del 1935. L'idea principale potrebbe essere stata la sua analisi del calcolo, o la sua realizzazione che esisteva una macchina universale e quindi un argomento diagonale per dimostrarne l'insolvibilità (...)

Il precoce interesse di Turing sulla macchina venne stimolato dalla macchina per scrivere della madre.

L'idea principale di Turing fu che l'Entscheidungsproblem di Hilbert potesse essere risolto attraverso un processo meccanico da una macchina (che successivamente venne teorizzata come la TM) e anche se gli giunse come illuminazione giovanile di una grande mente, in realtà aveva radici più profonde. Turing infatti per tutta la vita aveva dimostrato interesse nelle macchine, a partire dalle riflessioni infantili sulla macchina da scrivere della madre, che cercavano di estrapolarne le caratteristiche, che la determinavano appunto come macchina ^[14] .

La sua tesi di dottorato, intitolata " Systems of Logic Based on Ordinals ", contiene la seguente definizione di una "funzione calcolabile":

It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process'. We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author's definition of a computable function, and to an identification of computability with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions [the 3rd is the λ-calculus] are equivalent.
— Turing (1939) in The Undecidable ^[15]
È stato affermato in precedenza che "una funzione è effettivamente calcolabile se i suoi valori possono essere determinati mediante un processo puramente meccanico". Possiamo prendere questa affermazione alla lettera, intendendo per "processo puramente meccanico" quello che potrebbe essere eseguito da una macchina. È possibile fornire una descrizione matematica, in una certa forma normale, delle strutture di queste macchine. Lo sviluppo di queste idee porta alla definizione dell'autore di funzione calcolabile e all'identificazione del concetto di calcolabilità con quello di calcolabilità effettiva. Non è difficile, anche se un po' laborioso, dimostrare che queste tre definizioni [la terza è il λ-calcolo] sono equivalenti.

Quando Turing tornò in Inghilterra, dopo un periodo di formazione presso il college di Princeton , venne impiegato in ambito bellico dal governo inglese per infrangere i codici segreti tedeschi creati dalla macchina crittografica Enigma .

Venne poi coinvolto nella progettazione dell' ACE (Automatic Computing Engine): "la proposta ACE [di Turing] era effettivamente autonoma e le sue radici non risiedevano nell'EDVAC [l'iniziativa degli Stati Uniti], ma nella sua stessa macchina universale" (Hodges ^[16] ). Continuando così a sviluppare gli argomenti sull'origine e la natura di ciò che è stato nominato da Kleene (1952) la "tesi di Turing".

Ma ciò che Turing dimostrò con il suo modello di macchina computazionale apparve in forma definitiva solo nel suo articolo " On Computable Numbers, with a Application to the Entscheidungsproblem " (1937). In questo scritto infatti, per la prima volta concettualizza quella che diventerà la macchina di Turing:

[that] the Hilbert Entscheidungsproblem can have no solution... I propose therefore to show that there can be no general process for determining whether a given formula U of the functional calculus K is provable, ie that there can be no machine which, supplied with any one U of these formulae, will eventually say whether U is provable.
— The Undecidable ^[17]
[che] il "problema della fermata" di Hilbert non può avere soluzione... Propongo, quindi, di mostrare che non può esserci un processo generale per determinare se una data formula U del calcolo funzionale K è dimostrabile, cioè che non può esserci nessuna macchina a cui, data in ingresso una qualsiasi U di queste formule, alla fine dirà se U è dimostrabile.

1937–1970: Il "computer digitale", la nascita dell'"informatica"

Nel 1937 a Princeton, mentre stava lavorando alla sua tesi di dottorato, Turing costruì dal principio un moltiplicatore elettrico, realizzando i propri trasmettitori elettromeccanici. "Il compito di Alan era quello di incarnare la progettazione logica di una macchina Turing in una rete di trasmettitori azionati a interruttori..." ^[18] . Mentre Turing all'inizio sembrava essere solamente curioso, altri stavano andando nella stessa direzione sia in Germania ( Konrad Zuse , 1938), che negli Stati Uniti ( Howard Aiken e George Stibitz , 1937); i frutti delle loro fatiche furono usati dai militari dell'Asse e degli Alleati nella seconda guerra mondiale ^[19] .

Nella prima metà degli anni '50 Hao Wang e Marvin Minsky ridussero la macchina Turing a una forma più semplice (un precursore della macchina sviluppata poi da Martin Davis ); contemporaneamente anche i ricercatori europei stavano riducendo il nuovo computer elettronico a un oggetto teorico simile a quello che veniva chiamata "macchina di Turing".

Alla fine degli anni '50 e all'inizio degli anni '60, gli sviluppi paralleli e coincidenti di Melzak e Lambek (1961), Minsky (1961) e Shepherdson e Sturgis (1961) portarono avanti il lavoro europeo e ridussero la macchina di Turing a un computer più intuitivo, simile ad un modello astratto chiamato "contatore macchina"; Elgot e Robinson (1964), Hartmanis (1971), Cook e Reckhow (1973) svilupparono ancora il progetto con la "macchina a registro" ei modelli di "macchina ad accesso casuale" — ma fondamentalmente tutti sono "macchine di Turing multi-nastro" con aggiunti set di istruzioni aritmetiche.

1970-oggi: la macchina di Turing come modello computazionale

Oggi, le macchine per il calcolo, la registrazione e l'accesso casuale e la loro procreatrice macchina di Turing, continuano ad essere i modelli di scelta per i teorici che studiano questioni riguardanti la teoria della computazione. In particolare fa uso della macchina di Turing la teoria della complessità computazionale .

In base agli oggetti da manipolare nella computazione (numeri interi non-negativi o stringhe alfa-numeriche), due modelli hanno ottenuto una posizione dominante nella teoria basata sulle macchine complessa: la TM multinastro off-line e la RAM ( random access machine) di Cook e Reckhow anche se quest'ultima assume un ruolo principale solamente nelle aree relative all'analisi degli algoritmi. ^[20]

Varianti della macchina di Turing

In questo paragrafo le maggiori varianti della MdT definita in precedenza vengono presentate in termini discorsivi, lasciando ad articoli specifici le considerazioni più precise e complete.

Macchina di Turing multinastro

La MdT con più nastri differisce dalla classica sostanzialmente per il tipo della funzione di transizione; questa nel caso dei 3 nastri ha la forma

\delta ~:~S\times A\times A\times A\to S\times A\times \{-1,0,+1\}\times A\times \{-1,0,+1\}\times A\times \{-1,0,+1\}

\delta ~:~S\times A\times A\times A\to S\times A\times \{-1,0,+1\}\times A\times \{-1,0,+1\}\times A\times \{-1,0,+1\}

\delta ~:~S\times A\times A\times A\to S\times A\times \{-1,0,+1\}\times A\times \{-1,0,+1\}\times A\times \{-1,0,+1\}

.

Questa funzione si fa dipendere dalla transizione da quanto viene letto sulle caselle su cui si trovano le testine relative ai diversi nastri e stabilisce quali caratteri devono essere modificati sui vari nastri e come si devono eventualmente spostare le testine.

È abbastanza evidente come questa macchina sia più semplice da usare della classica. Ad es. con essa si possono agevolmente copiare stringhe da un nastro all'altro e con porzioni di nastro si possono rendere disponibili sequenze di memorie indirizzabili abbastanza agevolmente. Con una macchina a tre nastri si può implementare molto facilmente un'operazione aritmetica come la somma di due numeri espressi mediante cifre decimali. Similmente e con gli opportuni accorgimenti e con l'uso di altri opportuni registri, lo si può intuire, si riescono a implementare altre operazioni aritmetiche o su entità discrete.

Per dimostrare che una macchina a più nastri P ha la stessa portata di quelle ad un solo nastro si tratta di individuare una di queste, denotiamola M che consente di simularne le evoluzioni. Questa simulazione viene effettuata simulando su un solo nastro della M i molti nastri della P. Si possono avere configurazioni della M che simulano configurazioni della P utilizzando scritture particolari che separano le aree nelle quali sono riprodotti i diversi nastri della P e segnalano le posizioni sulle quali si trovano le varie testine di I/O. A ciascun passo della P si fa corrispondere una serie di passi della M con i quali si sistemano i vari nastri e le posizioni delle relative testine. Si può capire come con un gran numero di spostamenti e di cambiamenti di stato si possono simulare le mosse della P.

Macchina di Turing con memoria bidimensionale

Consente di simulare abbastanza facilmente macchine a più nastri e di effettuare elaborazioni grafiche. Ulteriori varianti possono servirsi di memorie tridimensionali e simili.

Macchina di Turing non deterministica

La macchina di Turing non deterministica si distingue da quella deterministica definita in precedenza per il fatto che, in presenza di un determinato stato e di un determinato carattere letto, essa permette più transizioni.

Definizione

Una macchina di Turing non deterministica T, con grado di non determinismo n, è così definita:

T=\langle S,s_{0},F,A,\beta ,n,\delta \rangle \quad

T=\langle S,s_{0},F,A,\beta ,n,\delta \rangle \quad

T=\langle S,s_{0},F,A,\beta ,n,\delta \rangle \quad

dove le sole differenze rispetto alla definizione iniziale riguardano la presenza dell'intero n e il genere della funzione di transizione:

\delta ~:~S\times A\to S\times (A\times \{-1,0,+1\})^{k}~{\mbox{ dove }}~k=1,2,...,n

\delta ~:~S\times A\to S\times (A\times \{-1,0,+1\})^{k}~{\mbox{ dove }}~k=1,2,...,n

\delta ~:~S\times A\to S\times (A\times \{-1,0,+1\})^{k}~{\mbox{ dove }}~k=1,2,...,n

Le sue configurazioni consistono quindi di insiemi finiti di configurazioni deterministiche, la cui cardinalità potrebbe crescere illimitatamente con il procedere di un'evoluzione.

Le computazioni che essa è in grado di svolgere sono descrivibili come insiemi di computazioni sviluppati da repliche della MdT deterministica, repliche che potrebbero rendersi necessarie ad ogni passo dell'evoluzione. Si osserva che questa richiesta oggi non dovrebbe affatto stupire, in quanto realizzabile con le tecniche dei computer collegati in rete ed effettivamente realizzata nella prassi delle elaborazioni distribuite.

Equivalenza con la MdT classica

Dato che ogni macchina deterministica si può considerare una particolare macchina non deterministica, si tratta di dimostrare che con una macchina deterministica M si riesce a simulare il comportamento di una macchina non deterministica N. Più precisamente supponiamo che N sia una macchina ad un nastro e che la M sia una macchina che dispone di una memoria bidimensionale, memoria assimilabile alla disponibilità di più nastri il cui numero sia aumentabile. La macchina M riesce a simulare con ciascuno dei suoi stati gli stati multipli della macchina N e con i suoi molti nastri i singoli nastri replicati della N. Ad ogni passo della N la M fa corrispondere una serie di passi con i quali fa evolvere i diversi nastri che rappresenta nella sua memoria bidimensionale e, in corrispondenza a una transizione non deterministica di molteplicità k, replica il nastro interessato trasformandolo nei k nastri richiesti.

In questo modo si vede come la macchina M possa simulare la N. Si osserva che alcuni singoli passi della macchina non deterministica richiedono un gran numero di passi e di appositi stati della deterministica.

Equivalenza tra MdT ak nastri e MdT ad un nastro

La capacità computazionale di una MdT non dipende dal numero di nastri che essa utilizza; questo è possibile dimostrarlo attraverso la simulazione. Indichiamo con T _k la macchina di Turing ak nastri e con T quella ad un nastro. Scriviamo l'input della macchina T _k sulla macchina T ovviamente un simbolo per ogni cella, quando la macchina T leggerà il primo simbolo essa per eseguire una quintupla della macchina T _k avrà bisogno di leggere k caratteri ricordando ogni volta il k-esimo carattere letto; verificato che la quintupla può essere eseguita a questo punto riporterà indietro la testina di k celle e può procedere all'esecuzione della quintupla sovrascrivendo ik caratteri; a questo punto la testina si troverà sulla cella contenente l'ultimo carattere scritto. Gli ultimi passaggi da eseguire sono il cambio di stato interno e il movimento della testina. È facile notare come l'insieme degli stati di T ha cardinalità maggiore rispetto all'insieme degli stati di T _k.

Macchine di Turing semplificate

Le macchine di Turing possono essere ulteriormente semplificate, senza perdita di portata computazionale. Le semplificazioni possibili sono (non attuabili contemporaneamente):

nastro illimitato solo in una direzione;
alfabeto di soli due caratteri, uno dei quali il simbolo blank;
solo due stati.

La dimostrazione dell'equivalenza con la macchina definita inizialmente con quelle con le caratteristiche 2 e 3 costituiscono il primo teorema di Shannon .

Un ulteriore modello semplificato di MdT è quello di avere tre MdT che compiono operazioni elementari (scrittura del carattere 1, scrittura del simbolo blank, spostamento della testina a destra, spostamento a sinistra, nessuna operazione) e ottenere da queste una nuova MdT tramite composizione per diramazione .

Macchina di Turing universale

Lo stesso argomento in dettaglio: Macchina di Turing universale .

La Macchina di Turing universale è quella che calcola la funzione u, che a sua volta è in grado di simulare il comportamento di qualunque macchina di Turing. La funzione u prende in input una codifica della macchina M che si voglia eseguire (ovvero un numero che una volta decodificato fornisca il codice di M) e una codifica dei parametri iniziali ad M.

Confronto con le macchine reali

La macchina di Turing, nonostante sia una "macchina astrattamente definita" ^[21] , è un ottimo modello per descrivere le macchine reali. In seguito alcune argomentazioni:

Tutto ciò che un computer reale può computare, lo può fare anche una TM. Per esempio: "Una macchina di Turing può simulare ogni tipo di subroutine trovato nei linguaggi di programmazione, incluse procedure ricorsive e ognuno dei parametri di passaggio del meccanismo conosciuti" ( Hopcroft and Ullman ^[22] ) . Anche un automa a stati finiti (FSA) sufficientemente capiente può imitare ogni computer reale, trascurando l'IO. Perciò, uno statuto sulle limitazioni della macchina di Turing sarebbe applicato anche ai computer reali.
La differenza sta solo nella capacità di una TM di manipolare una quantità illimitata di dati. Comunque, dato un tempo finito, una TM (come una macchina reale) può processare una quantità finita di dati.
Come una TM, una macchina reale può allargare il suo spazio di archiviazione secondo necessità, acquisendo dischi aggiuntivi o altri sistemi di archiviazione.
Le descrizioni di programmi per macchine reali, usando semplici modelli astratti, sono spesso molto più complesse di descrizioni ottenute usando la macchina di Turing. Per esempio, una TM può assumere poche centinaia di stadi descrivendo un algoritmo, mentre un automa a stati finiti deterministico (DFA) equivalente ne fornirebbe quadrillioni partendo da una macchina reale data. Questo rende le rappresentazioni del DFA impossibili da analizzare.
Le macchine di Turing descrivono algoritmi indipendentemente da quanta memoria utilizzano. Ogni macchina corrente possiede dei limiti di memoria contenuta, ma questi limiti possono essere ampliati nel tempo arbitrariamente. Le macchine di Turing ci permettono di produrre enunciati sugli algoritmi che (teoricamente) avranno valore eterno, indipendentemente da evoluzioni nell'architettura convenzionale della meccanica dei computer.
Le TM semplificano i postulati degli algoritmi. Infatti algoritmi che girano su una macchina Turing-equivalente astratta sono generalmente più astratti delle loro controparti su macchine reali, perché hanno una precisione arbitraria delle tipologie di dati possibili e non devono mai tener conto di condizioni impreviste (inclusi, ma non solo, casi di memoria limitata).

Note

^ TecaLibri: Yurij Castelfranchi: Macchine come noi
^ ^ Babbage's Analytical Engine, 1834-1871. (Trial model) Archiviato il 20 settembre 2010 in Internet Archive . - Museo delle Scienze, Londra
^ Gandy, Robin Oliver, On axiomatic systems in mathematics and theories in physics .
^ Robin Gandy,, The Confluence of Ideas in 1936 , p. 54.
^ ^a ^b Robin Gandy, The Confluence of Ideas in 1936 , p. 53.
^ ^a ^b Robin Gandy, The Confluence of Ideas in 1936 , pp. 52-53.
^ N. Dershowitz e Y. Gurevich, A Natural Axiomatization of Computability and Proof of Church's Thesis , 2008.
^ Robin Gandy, The Confluence of Ideas in 1936 , p. 57.
^ Andrew Hodges, Alan Turing: The Enigma , pp. 126-127.
^ A. Hodges, Alan Turing. Storia di un Enigma , 1991, p. 112.
^ Andrew Hodges, Alan Turing: The Enigma , p. 129.
^ Robin Gandy, The Confluence of Ideas in 1936 , p. 74.
^ Robin Gandy, The Confluence of Ideas in 1936 , p. 76.
^ Andrew Hodges, Alan Turing Storia di un enigma , pp. 133-134.
^ A. Turing, The Undecidable , p. 160.
^ Andrew Hodges, Alan Turing: The Enigma , p. 318.
^ A. Turing, The Undecidable , p. 145.
^ Andrew Hodges, Alan Turing: The Enigma , p. 138.
^ Andrew Hodges, Alan Turing: The Enigma , pp. 298-299.
^ van Emde Boas, Machine Models and simulation , 1990.
^ AM Turing - Enciclopedia Treccani , su treccani.it .
^ Hopcroft e Ullman, Introduction to Automata Theory, Languages, and Computation , p. 157.

Bibliografia

Libri

A. Hodges, Alan Turing. Storia di un Enigma , Torino, Bollati Boringhieri, 1991 [1983] .
J. Hopcroft , J. Ullman (1979), Introduction to Automata Theory, Languages and Computation , Addison-Wesley ISBN 0-201-02988-X
- Versione italiana: J. Hopcroft, R. Motwani, J. Ullman, Automi, linguaggi e calcolabilità, Pearson, 2003, ISBN 978-88-7192-552-3
Douglas Hofstadter (1979), Gödel, Escher, Bach: an Eternal Golden Braid
- Versione italiana: Godel, Escher, Bach: un'eterna ghirlanda brillante , Adelphi, Milano, 1990, ISBN 88-459-0755-4
Arto Salomaa, Computation and automata , Cambridge University Press, 1985, ISBN 0-521-30245-5
Ivor Grattan-Guiness, The search for Mathematical Roots, 1870-1940 , Princeton University Press, 2000, ISBN 0-691-05858-X
( EN ) Jackson, Philip C., Introduction to artificial intelligence .
Arbib, Michael A., La mente, le macchine e la matematica .
Davis, Martin, Il calcolatore universale , Milano, Adelphi, 2003, ISBN 9788845917929 .
Cappuccio, Massimiliano, Alan Turing: L'uomo, La macchina, L'enigma , Milano, AlboVerso, 2005, ISBN 88-89130-29-6 .
Stillwell, John, Da Pitagora a Turing , Bologna, ETS, 2018, ISBN 978-884675042-6 .
Martin Davis, The Undecidable , Dover Pubns; Dover edizione, 2004, ISBN 0486432289 .
Robin Gandy, The Confluence of Ideas in 1936 , 1988.

Articoli

Alan Turing (1936): On computable numbers, with an application to the Entscheidungsproblem , Proc. London Math. Soc., 42 pp. 230–265 Accessibile anche in linea

Voci correlate

Macchine equivalenti alla MdT

Altri progetti

Wikiversità contiene risorse su macchina di Turing
Wikimedia Commons contiene immagini o altri file su macchina di Turing

Collegamenti esterni

( EN ) Macchina di Turing , su Enciclopedia Britannica , Encyclopædia Britannica, Inc.
( EN ) Turing Machine in MathWorld
( EN ) Turing Machine nella Stanford Encyclopedia of Philosophy
Andrea de Prisco, Algoritmi e Macchine di Turing ( JPG ), in MCmicrocomputer , n. 59, Roma, Technimedia, gennaio 1988, p. 120, ISSN 1123-2714 ( WC · ACNP ) .
Articolo divulgativo , su startmag.it .

Simulatori

Scritto in Python qui
Scritto in JavaScript : JSTMSimulator ( codice su GitHub )
Scritto in Java : l' applet e il codice
Scritto in Objective C per iPad: [1]

Teoria degli automi : linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica formale	Linguaggio	Automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Dipendente dal contesto	Dipendente dal contesto	Automa lineare
Tipo-2	Libera dal contesto	Libero dal contesto	Automa a pila ND
Tipo-3	Regolare	Regolare	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme proprio della categoria immediatamente sovrastante.

Controllo di autorità	LCCN ( EN ) sh85138778 · GND ( DE ) 4203525-9 · BNF ( FR ) cb11978871z (data) · BNE ( ES ) XX550362 (data) · NDL ( EN , JA ) 00573533

Portale Informatica

Portale Matematica

Portale Scienza e tecnica

[1] TecaLibri: Yurij Castelfranchi: Macchine come noi

[2] Babbage's Analytical Engine, 1834-1871. (Trial model) Archiviato il 20 settembre 2010 in Internet Archive . - Museo delle Scienze, Londra

[3] Gandy, Robin Oliver, On axiomatic systems in mathematics and theories in physics .

[4] Robin Gandy,, The Confluence of Ideas in 1936 , p. 54.

[:2-5] Robin Gandy, The Confluence of Ideas in 1936 , p. 53.

[:3-6] Robin Gandy, The Confluence of Ideas in 1936 , pp. 52-53.

[7] N. Dershowitz e Y. Gurevich, A Natural Axiomatization of Computability and Proof of Church's Thesis , 2008.

[8] Robin Gandy, The Confluence of Ideas in 1936 , p. 57.

[9] Andrew Hodges, Alan Turing: The Enigma , pp. 126-127.

[:1-10] A. Hodges, Alan Turing. Storia di un Enigma , 1991, p. 112.

[11] Andrew Hodges, Alan Turing: The Enigma , p. 129.

[12] Robin Gandy, The Confluence of Ideas in 1936 , p. 74.

[13] Robin Gandy, The Confluence of Ideas in 1936 , p. 76.

[14] Andrew Hodges, Alan Turing Storia di un enigma , pp. 133-134.

[15] A. Turing, The Undecidable , p. 160.

[16] Andrew Hodges, Alan Turing: The Enigma , p. 318.

[17] A. Turing, The Undecidable , p. 145.

[18] Andrew Hodges, Alan Turing: The Enigma , p. 138.

[19] Andrew Hodges, Alan Turing: The Enigma , pp. 298-299.

[20] van Emde Boas, Machine Models and simulation , 1990.

[21] AM Turing - Enciclopedia Treccani , su treccani.it .

[22] Hopcroft e Ullman, Introduction to Automata Theory, Languages, and Computation , p. 157.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[ 9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]