inteligenta-artificiala.ro - Printare "Masina Turing"

Maşinile Turing sunt nişte modele 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 a fost niciodată construite. Studiul proprietăţilor lor abstracte este util în informatică şi teoria complexităţii.

Conjectura Church-Turing postulează că orice problemă de calcul bazată pe o procedură algoritmică poate fi rezolvată de către o maşină Turing. Această "conjectură" nu are o formulare matematică, deoarece nu se bazează pe o definiţie precisă a conceptului de procedură algoritmică. Î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).

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 împletiit 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. Această "conjectură" nu are o formulare matematică, deoarece nu se bazează pe o definiţie precisă a conceptului de procedură algoritmică. Î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 casuţ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.)

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

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 k benzi

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.

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.

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.

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.

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ă Turingcare 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 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 states ş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.