capitolul 5 maŞini turing
TRANSCRIPT
CAPITOLUL 5
MAŞINI TURING
5.1. INTRODUCERE ŞI DEFINIŢII
În capitolele precedente am introdus diferite tipuri de dispozitive
automate, cum sunt maşinile cu stări finite şi automatele push-down, care
sunt menite să recunoască limbaje generate de gramatici. Numărul
tipurilor de limbaje recunoscute de automatele finite a fost foarte restrâns
– limbaje cu gramatică regulară. Automatele push-down s-au dovedit a fi
dispozitive mai puternice; de fapt, orice limbaj independent de context a
fost recunoscut de un APD (eventual nedeterminist). Dar, chiar şi
maşinile au limitele lor; de pildă, un limbaj aparent simplu
{ | 0,1,2, }n n na b c n = K nu este recunoscut de nici un PDA. (Vezi exemplul
4.6.) Am discutat şi maşini cu output (paragrafele 3.4. şi 4.3). Ele pot fi
văzute ca modele matematice a unui concept de algoritm intuitiv: Pentru
un input dat (sub forma unui şir finit de simboluri pe o bandă), maşina
operează asupra acestui input şi produce diferite output-uri. Procesul de
calcul în aceste maşini constă în schimbarea stărilor interne şi
modificarea diferiţilor pointeri (input, stivă şi/sau output). În acest capitol
vom studia un alt dispozitiv, numit maşină Turing, care înglobează toate
aceste caracteristici, şi este mai puternică decât toate maşinile discutate
până acuma. Maşinile Turing par a fi cele mai puternice dispozitive
automate posibile – ele sunt în esenţă definiţia matematică exactă, a
conceptului de algoritm sau procedură. Din acest motiv au fost introduse
în 1936 de Alan Turing, vezi [19]. Vom discuta aceste idei mai târziu, dar
în esenţă avem următoarea situaţie.
Un algoritm poate fi văzut ca o mulţime de instrucţiuni, sau dacă
dorim ca o „carte de bucate”, folosită de o maşină care va acţiona asupra
diferitelor tipuri de input-uri. Input-urile pot fi văzute ca o mulţime finită
de simboluri care urmează a fi citite de o maşină (unul câte unul), şi
programul sau instrucţiunile care arată maşinii ce are de făcut după citirea
fiecărui astfel de simbol. În esenţă, acesta este comportamentul maşinilor
Turing, însă partea interesantă este faptul că orice definire rezonabilă,
precisă a unui algoritm este echivalentă cu conceptul de maşină Turing.
Pe de altă parte, un algoritm este definit ca o maşină Turing.
În esenţă, o maşină Turing este compusă dintr-un număr finit de
stări şi o bandă. Banda este împărţită într-un număr infinit (numerabil) de
celule şi este infinită la dreapta. Maşinile Turing pot fi reprezentate ca în
figura 5.1.
Figura 5.1. O maşină Turing.
Maşina are în plus un pointer (cap) de citire/scriere care în otice moment
dat punctează spre una dintre celulele de pe bandă. De asemenea mai ar o
mulţime finită Σ de simboluri, numită alfabetul benzii. Elementele din Σ
sunt simbolurile admise în celulele de pe bandă – un simbol pe celulă.
Unul dintre aceste simboluri este dedicat şi se numeşte simbolul blank, îl
vom nota întotdeauna cu #. Dacă simbolul # apare într-o celulă spunem
că celula este blank. În orice moment dat există doar un număr finit de
celule care conţin un simbol ne-blank, toate celelalte celule sunt blank.
Aşadar, toate celulele din dreapta unei celule sunt blank. Maşina operează
în paşi discreţi. La orice moment dat se află într-o stare Q iar capul ei de
citire punctează spre o celulă care conţine un simbol x∈Σ . Pe baza
acestor informaţii şi numai acestora, maşina efectuează următoarele trei
operaţii:
1. Trece într-o stare nouă Q .
2. Înlocuieşte simbolul x, scanat anterior de capul de citire, cu alt
simbol x din Σ .
3. Mută capul cu o celulă la dreapta sau la stânga, sau deloc.
Aceste trei acţiuni, executate împreună, se numesc mişcare. După
efectuarea unei mişcări maşina se află într-o altă stare şi citeşte alt
simbol, deci execută altă mişcare iar procedeul se repetă. Iniţial, maşina
se află într-o stare iniţială specială, pe care de obicei o vom nota 0Q iar
banda este umplută cu secvenţe de simboluri din Σ . Conţinutul iniţial al
benzii va fi numit input. Vom presupune întotdeauna că input-ul conţine
doar un număr finit de celule ne-blank. Aşadar, cu aceste setări iniţiale,
maşina intră în execuţie. Ea se va opri în următoarele trei situaţii:
1. Una din stările maşinii este desemnată ca stare de oprire şi va fi
întotdeauna notată cu H. După ce maşina intră în această stare H ea se
opreşte şi-şi termină activitate. Spunem în acest caz că maşina s-a oprit.
2. Capul de citire/scriere punctează spre cea mai din stânga celulă
de pe bandă şi instrucţiunile cer capului să se deplaseze cu o celulă la
dreapta. În această situaţie maşina încetează să opereze; vom spune că
maşina s-a blocat.
3. Pentru starea curentă şi simbolul pe care se află poziţionat capul
nu există instrucţiuni în programul maşinii. Dacă aceasta are loc, spunem
de asemenea că maşina s-a blocat.
Aşadar, fiind dar un input-ul iniţial, maşina începe în starea iniţială
0Q şi trece prin stări în timp ce operează asupra benzii de intrare. Ea poate
acţiona nedefinit, se poate opri sau se poate bloca. Formal avem:
Definiţia 5.1. O maşină Turing T se compune din următoarele
patru obiecte:
1. O mulţime finită de stări Q. Unul dintre elementele din Q este
denotat prin H şi se numeşte starea de oprire.
2. O mulţime finită de simboluri Σ , numită alfabetul benzii. Unul
dintre elementele din Σ este # şi poartă denumirea de simbol
blank. Se presupune că simbolurile L, R, şi S nu aparţin lui Σ .
3. O stare specificată 0Q din Q numită stare iniţială.
4. O funcţie de tranziţie ( , )Q xδ definită pentru toate perechile de
forma ( , )Q x unde QQ∈ (Q H≠ ) şi x∈Σ . Valoarea lui ( , )Q xδ
este un triplet ˆ ˆ( , , )Q x N unde QQ∈ , x∈Σ şi , , sau N L R S= .
Formal,
: (Q \{ }) { , , }H Q L R Sδ ×Σ→ ×Σ× ,
cu precizarea că funcţia δ nu trebuie să fie definită pentru toate
valorile de Q şi x.
O astfel de maşină Turing se notează 0{ , , , }T Q Q δ= Σ . Funcţia de
tranziţie ˆ ˆ( , ) ( , , )Q x Q x Nδ = se interpretează astfel: Dacă maşina se află în
starea Q şi capul ei de citire/scriere punctează la simbolul x, atunci T trece
în starea Q , înlocuieşte x cu x şi deplasează capul cu o celulă spre
dreapta ( N R= ), o celulă spre stânga (dacă N I= ) sau rămâne neschimbat
(dacă N S= ).
Înainte de a prezenta un exemplu, vom elabora o notaţie pentru
descrierea configuraţiilor maşinilor Turing. Întrucât în orice moment dat
banda maşinii conţine doar un număr finit de simboluri ne-blank,
conţinutul unei astfel de benzi este descris complet prin listarea părţii
stângi a benzii inclusiv ultimul simbol ne-blank. Pentru evitarea unor
ambiguităţi – de pildă, când banda este complet goală – descriem
conţinutul benzii cu trei simboluri: 1σ , x şi 2σ , unde 1σ este conţinutul
benzii din partea dreaptă a capului, inclusiv ultimul simbol ne-blank.
Fiecare dintre şirurile 1σ şi 2σ poate fi şirul vid λ : Dacă 1σ λ= , capul
punctează la cea mai din stânga celulă a benzii, dacă 2σ λ= , toate celulele
din dreapta capului sunt blank (adică, conţin simbolul #). Configuraţia
unei maşini Turing este atunci definită ca fiind cvadruplul 1 2, , , Q xσ σ ,
unde Q este starea curentă iar 1σ , x şi 2σ sunt cele descrise mai sus.
Astfel, de exemplu, configuraţiile (i) şi (ii) din figura 5.2. sunt
4 , # , #, Q a ba a respectiv 5 , , #, Q aba λ . Dacă nu există pericol de
confuzie, este convenabil să combinăm şirurile 1σ , x şi 2σ într-un singur
şir 1 2xσ σ şi să subliniem poziţia capului (adică, simbolul x). Aşadar,
1 2, , , Q xσ σ este scrisă ca 1 2, , , Q xσ σ . Configuraţiile din figura 5.2.
vor fi atunci 4 , # #Q a ba a şi 5 , #Q aba . Configuraţia unei maşini într-o
stare Q, cu banda complet goală şi cu capul punctând spre celula cea mai
din stânga este atunci , #Q .
Figura 5.2. Configuraţia unei maşini Turing.
Presupunem acum că maşina Turing se află în configuraţia
1 2, Q xσ σ şi în urma aplicării unei funcţii de tranziţie δ trece în
configuraţia 1 2ˆ ˆ ˆ ˆ, Q xσ σ . Notăm aceasta
1 2 1 2ˆ ˆ ˆ ˆ, , Q x Q xσ σ σ σ→
Dacă maşina T trece din configuraţia 1 2, Q xσ σ în 1 2ˆ ˆ ˆ ˆ, Q xσ σ printr-o
secvenţă de mai multe mişcări, notăm aceasta
*
1 2 1 2ˆ ˆ ˆ ˆ, , Q x Q xσ σ σ σ→
Notaţia aceasta este complet analoagă cu cea folosită la descrierea
mişcărilor unei maşini cu stări finite sau automat push-down. În aceeaşi
manieră, maşinile Turing pot fi reprezentate prin diagrame similare celor
ale maşinilor cu stări finite. Dacă 0{Q, , , }T Q δ= Σ este o maşină Turing,
(i) (ii)
pentru fiecare valoare ˆ ˆˆ( , ) ( , , )Q x Q x Nδ = desenăm o săgeată între stările Q
şi Q , ca în figura 5.3.
Figura 5.3. Tranziţia unei maşini Turing.
5.2. MAŞINI TURING CA PROCEDURI DE DECIZIE
Maşinile Turing pot fi utilizate ca acceptori de limbaje. Prin
aceasta înţelegem că o maşină Turing LT T= recunoaşte un limbaj L dat,
dacă T poate determina dacă un şir σ este în L sau nu. O astfel de maşină
Turing este văzută ca o „procedură de decizie” de apartenenţă la un
limbaj. Aceasta este analog cazului maşinilor cu stări finite. Caz în care,
dat fiind un limbaj L şi o MSF M care recunoaşte L, am putut determina
pentru orice şir σ dacă aparţine sau nu lui L. Procedura era simplă: Am
pornit M în starea iniţială cu input-ul σ şi am observat comportamentul
lui M. Dacă M s-a oprit într-o stare acceptată, σ era în L, dacă M s-a oprit
într-o stare neacceptată σ n-a fost în L. În cazul maşinilor Turing,
informaţia dacă un şir dat aparţine sau nu limbajului, este afişat pe bandă.
Formal avem următoarele.
Definiţia 5.2. Presupunem că L este un limbaj peste un alfabet Σ ;
pentru simplificare presupunem că Σ nu conţine simbolurile # şi $.
Spunem că L este recunoscut în sens Turing, dacă există o maşină Turing
LT T= cu următoarele proprietăţi:
unde , sau N L R S=
1. Alfabetul de bandă a lui T conţine { , #}SΣ∪ (poate conţine şi alte
simboluri);
2. Presupunem că σ este un şir de simboluri din Σ ( *σ ∈Σ ) şi
considerăm maşina T în configuraţia iniţială 0 , $Q σ . Dacă σ este
în L, maşina T se va opri în configuraţia , $H Y ;
*
0 , $ , $Q H Yσ → pentru Lσ ∈ ;
Dacă σ nu este în L, atunci maşina se va opri în configuraţia
, $H N :
*
0 , $ , $Q H Nσ → pentru Lσ ∉ .
Maşina Turing trebuie să se oprească pentru toate input-urile valide,
adică, ori de câte ori este pornită în configuraţia 0 , $Q σ cu *σ ∈Σ .
Aceasta înseamnă că T poate decide problema apartenenţei pentru orice
şir *σ ∈Σ . Din acest motiv, limbajele recunoscute de o maşină Turing se
numesc şi recunoscute în sens Turing. Deci, un limbaj poate fi descris şi
de o maşină Turing bazat pe faptul dacă maşina se opreşte, sau nu, cu un
şir dat. Spunem că un limbaj este acceptat de o maşină Turing LT T= dacă
L se compune din acei σ pentru care T, eventual, odată pornit în
configuraţia 0 , $Q σ , se va opri (conţinutul benzii în momentul intrării
în starea de oprire este vid). Dacă un limbajul L este acceptat de o maşină
Turing, spunem că L este acceptabil Turing. Această metodă de descriere
a unui limbaj este complet diferită de ceea dată anterior şi o vom discuta
detaliat în capitolul 9. Pentru clarificarea acestor concepte, să considerăm
unele exemple.
Exemplu 5.1. Vom proiecta o maşină Turing care va recunoaşte
limbajul
{1 | 1,3,5, }nL n= = K
adică, limbajul şirurilor formate dintr-un număr impar de 1-uri. Ideea de
bază a unei astfel de maşini T este următoarea: Pornită în configuraţia
0 , $11 1Q K va muta capul spre dreapta, alternând între două stări pentru
a contoriza numărul de 1-uri, până când întâlneşte #. Atunci se va deplasa
la stânga, înlocuind toate simbolurile de bandă cu #, până ce ajunge
capătul stâng al benzii; apoi scrie Z pe bandă şi se opreşte. Descrierea
formală a maşinii este următoarea:
1. Alfabetul Σ este {$, 1, , , #}Y N .
2. Stările sunt: 0Q , starea iniţială; 1Q , număr par de 1-uri întâlnite
până aici; 2Q , număr impar de 1-uri întâlnite până aici; 3Q , numărul
de 1-uri din σ este par, mută capul înapoi pe $; 4Q , numărul de
1-uri din σ este impar, mută capul înapoi pe $; 5Q , scrie Y şi se
opreşte; 6Q , scrie N şi se opreşte; H, starea de oprire.
3. Funcţia de tranziţie δ este dată de diagrama din figura 5.4.
Figura 5.4. Maşină Turing care recunoaşte un limbaj.
În figura 5.5. valorile funcţiei de tranziţie sunt date sub formă tabelară.
Funcţia δ nu este definită pentru toate valorile de Q şi x. Considerăm
acum, ca exemplu, mişcările maşinii la input-urile 1 111σ = şi 2 1111σ = .
Cu input-ul 1σ avem
0 1 2 1
2 4 4 4
4 6
, $111 , $111 , $111 , $111, $111# , $111 , $11 , $1, $ , $ # , $ se opreşte, şirul de intrare este în .
Q Q Q QQ Q Q QQ Q H H L
→ → →→ → → →→ → → −
Simbol de bandă x
1 $ # Y N
0Q 1( , $, )Q R
1Q 2( , 1, )Q R 3( , #, )Q L
2Q 1( , 1, )Q R 4( , #, )Q L
3Q 3( , #, )Q L 5( , $, )Q L 3( , #, )Q L
4Q 4( , #, )Q L 6( , $, )Q R 4( , #, )Q L
5Q ( , , )H N L
6Q ( , , )H N L
S
t
a
r
e
H
Figura 5.5. Valorile funcţie de tranziţie δ .
Cu input-ul 2σ avem
0 1 2 1
2 1 3 3
3 3 3 5
, $1111 , $1111 , $1111 , $1111, $1111 , $1111# , $1111 , $111, $11 , $1 , $ , $ # , $
se opreşte, şirul de intrare nu este în .
Q Q Q QQ Q Q QQ Q Q Q H N
L
→ → →→ → → →→ → → → →
−
Această maşină, fiind simplă şi directă, nu este foarte interesantă.
Limbajul din cauză a fost deja recunoscut de un automat finit. Dăm acum
un exemplu de maşină Turing care va recunoaşte limbajul
{ | 0,1, 2, }n n nL a b c n= = K , despre care ştim că nu este acceptat de vreun
automat push-down, vezi exemplul 4.7.
Exemplu 5.2. Construim o maşină Turing care recunoaşte limbajul
{ | 0,1, 2, }n n nL a b c n= = K . Maşina T se va comporta în felul următor: Fiind
dat un şir σ de a-uri, b-uri şi c-uri ( *( )σ ∈ + +a b c ), maşina, odată pornită
în configuraţia 0 , $Q σ , se va opri în configuraţia , $H Y dacă c
aparţine limbajului sau în , $H N dacă σ nu aparţine limbajului. O
scurtă privire asupra operaţiilor ei este următoarea:
1. Va avea stările 1C , 2C , 3C . Dacă T decide că σ aparţine limbajului,
va intra în starea 1C urmând să „golească banda” şi se opreşte în
configuraţia , $H Y .
2. Va avea stările 1D , 2D , 3D . Dacă T decide că σ nu aparţine
limbajului, va intra în starea 1D şi trece în configuraţia , $H N .
3. Va utiliza stările 1 5E E− pentru a determina dacă σ este de formai j ka b c , adică, dacă * * *σ ∈a b c . Aceasta se face, începând din
configuraţia 1, $E σ , prin deplasarea capului spre dreapta şi
intrarea în starea 2E . Dacă este întâlnit a, capul continuă să se
deplaseze la dreapta aşteptând apariţia lui b, la care T intră în starea
3E . Capul se deplasează atunci din nou spre dreapta până când este
întâlnit c iar starea se schimbă în 4E . Capul continuă deplasarea
spre dreapta până ce întâlneşte #, deci * * *σ ∈a b c . Dacă ceva merge
greşit, maşina intră în starea 1D .
4. Mai departe, se determină dacă numărul de a-uri, b-uri şi c-uri este
acelaşi. În aceste moment se ştie deja că şirul σ este de formai j ka b c , deci mai trebuie verificat dacă i j= şi j k= . Pentru a
verifica că numărul de a-uri şi b-uri este acelaşi, capul este
poziţionat la începutul şirului şi oscilează, înainte şi înapoi, între
a-uri şi b-uri. De fiecare dată când întâlneşte un a, acesta se
schimbă în p, iar capul se deplasează la dreapta pentru a găsi un b.
Odată găsit, este schimbat în q, iar capul se deplasează înapoi
pentru a găsi alt a. Dacă nu mai găseşte nici unul, maşina verifică
dacă există b-uri nemarcate, adică, dacă toţi b au fost schimbaţi în
q-uri. Din nou, dacă merge ceva greşit, maşina intră în starea 1D .
Toate acestea au loc în timp ce maşina rămâne într-una din stările
1F , 2F , 3F , 4F . Mai rămâne de arătat că numărul de p-uri este egal
cu numărul de c-uri (fiecare a a fost schimbat în p, deci există
atâtea p-uri câţi au fost de a). Aceasta are loc în timp ce maşina se
mişcă între stările 1G , 2G , 3G ; ideea este aceeaşi ca la compararea
de a-uri şi b-uri.
Aceasta nu este cea mai eficientă modalitate de construire a maşinii
discutate; schema a fost aleasă doar din motive de claritate. Formalităţile
construcţie sunt următoarele:
1. Maşina are următoarele stări:
0Q , 1Q – pentru pornirea operaţiei; (aici se determină şi dacă σ λ= )
1C , 2C , 3C – pentru golire după ce s-a determinat că Lσ ∈
1D , 2D , 3D – pentru golire dacă s-a determinat că Lσ ∉
1E , 2E , 3E , 4E , 5E – pentru a determina dacă * * *σ ∈a b c
1F , 2F , 3F , 4F – pentru a determina dacă numărul de a-uri şi b-uri
este acelaşi
1G , 2G , 3G – pentru a determina dacă numărul de a-uri şi c-uri este
acelaşi
2. Alfabetul benzii este {$, , , , , , , , , , #}a b c p q r s Y NΣ = .
3. Starea iniţială este 0Q .
4. Funcţia de tranziţie δ este dată după cum urmează:
Stările 1C , 2C şi 3C : Dacă maşina intră în starea 1C , a determinat că
şirul σ este în limbaj iar tot ce rămâne de făcut sunt operaţii de
golire:
1 1( , ) ( , , )C x C x Rδ = pentru toţi #x ≠ (Localizează primul simbol din
dreapta)
1 2( , #) ( , #, )C C Lδ =
2 2( , ) ( , , )C x C x Lδ = pentru toţi $x ≠ (Şterge toate simbolurile de pe
bandă exceptând $)
2 3( , $) ( , $, )C C Rδ =
3( , #) ( , , )C H Y Lδ = – Scrie Y pe bandă şi se opreşte.
Stările 1D , 2D şi 3D : Mişcările sunt la fel ca mai sus, cu excepţia că
simbolul N trebuie scris la sfârşit:
1 1( , ) ( , , )D x D x Rδ = pentru toţi #x ≠ 1 2( , #) ( , #, )D D Lδ =
2 2( , ) ( , #, )D x D Lδ = pentru toţi $x ≠ 2 3( , $) ( , $, )D D Rδ =
3( , #) ( , , )D H N Lδ =
Stările 1 5E E− . Pornim în configuraţia 1, $E σ , ne deplasăm la
dreapta, aşteptând să găsim un şir de a-uri urmat de o secvenţă de
b-uri, urmate de c-uri iar în final #. Dacă aceasta are loc, întoarcem
capul la $ şi trecem la următoarea etapă. Orice deviere de la ceea
ce ne aşteptăm rezultă în schimbarea în starea 1D . Avem:
1 2( , $) ( , $, )E E Rδ = 2 2( , ) ( , , )E a E a Rδ =
2 3( , ) ( , , )E b E b Rδ = 3 3( , ) ( , , )E b E b Rδ =
3 4( , ) ( , , )E c E c Rδ = 4 4( , ) ( , , )E c E c Rδ =
4 5( , #) ( , #, )E E Lδ =
În acest moment maşina a determinat că * * *σ ∈a b c , deci trebuie să
mute capul înapoi la $ şi să continue cu următorul set de teste:
4 5( , ) ( , , )E x E x Lδ = pentru toţi $x ≠ , 5 1( , $) ( , $, )E F Sδ = . În toate
celelalte cazuri, 1( , ) ( , , )jE x D x Rδ = . (Continuă cu respingere.)
Stările 1 4F F− : Obiectivul este aici de a determina dacă numărul de
a-uri este acelaşi cu numărul de b-uri. Întrucât am ajuns
configuraţia 1, $F σ , suntem asiguraţi că σ este de forma i j ka b c .
Începem cu mutarea capului spre dreapta până la găsirea lui a.
Atunci starea va fi schimbată în 2F şi a înlocuit cu p. Capul va
continua să se deplaseze la dreapta (presupunând numai a-uri şi
q-uri pe acest drum) până ce întâlneşte un b. La întâlnirea unui b,
acesta se schimbă în q, capul se întoarce la celula cea mai din
stânga ($) şi procedeul începe de la început. Şirul σ trece de testul
de apartenenţă la L dacă începând de la $ şi mergând spre dreapta,
maşina nu găseşte nici un a sau b – tot ce vede sunt p-uri şi q-uri
iar apoi dă de un c. Detaliat avem:
1 1( , ) ( , , )F x F x Rδ = pentru $, ,x p q= ; 1 2( , ) ( , , )F a F p Rδ = (Găseşte şi
marchează un a.)
2 2( , ) ( , , )F x F x Rδ = pentru ,x a q= ; 2 3( , ) ( , , )F b F q Lδ = (Găseşte şi
marchează un b.)
3 3( , ) ( , , )F x F x Lδ = pentru $x ≠ ; 3 1( , $) ( , $, )F F Rδ = (Începe din nou
căutarea unui a.)
1 4( , ) ( , , )F c F c Lδ = ; (Toate a-urile şi b-urile sunt potrivite, este
timpul pentru a vedea dacă numărul de p-uri este egal cu numărul
de c-uri.)
4 4( , ) ( , , )F x F x Lδ = pentru toţi $x ≠ ; 4 1( , $) ( , $, )F G Sδ =
În toate celelalte situaţii 1( , ) ( , , )jF x D x Rδ = (şirul nu este din L).
Stările 1 3G G− . Aici se determină dacă numărul se a-uri (p-uri) este
egal cu numărul de c-uri. Ideea de bază este analoagă
comportamentului din stările F; formularea exactă este următoarea:
1 1( , ) ( , , )G x G x Rδ = pentru $, , ,x r p s= ; 1 2( , ) ( , , )G p G r Rδ = (Găseşte
şi marchează un p.)
2 2( , ) ( , , )G x G x Rδ = pentru , ,x p q s= ; 2 3( , ) ( , , )G c G s Lδ = (Găseşte şi
marchează un c.)
3 3( , ) ( , , )G x G x Lδ = pentru $x ≠ ; 3 1( , $) ( , $, )G G Rδ = (Caută din nou
un p.)
1 1( , #) ( , #, )G C Lδ = (Numărul de p-uri este egal cu numărul de c-uri
deci Lσ ∈ .)
În toate celelalte situaţii 1( , ) ( , , )jG x D x Rδ = .
În final, întreaga operaţia începe în configuraţia 0 , $Q σ . Aşadar:
0 1( , $) ( , $, )Q Q Rδ = ; 1 1( , #) ( , #, )Q C Rδ = (şirul σ λ= , continuă
pentru acceptare)
1 1( , ) ( , , )Q x E x Lδ = pentru restul de x-uri. (Începe cu testarea.)
Ilustrăm comportarea lui T cu input-ul aabbccσ = . Mişcările sunt:
0 1 1 2
2 2 3 3
4 4 5 5
5 5 5
, $ , $ , $ , $, $ , $ , $ , $, $ , $ # , $ , $, $ , $
Q aabbcc Q aabbcc E aabbcc E aabbccE aabbcc E aabbcc E aabbcc E aabbccE aabbcc E aabbcc E aabbcc E aabbccE aabbcc E aabbcc E
→ → →→ → → →→ → → →
→ → → 5
5 1 1 2
2 3 3 3
1 1 2 2
3
, $ , $, $ , $ , $ , $, $ , $ , $ , $
, $ , $ , $ , $
, $
aabbcc E aabbccE aabbcc F aabbcc F aabbcc F pabbccF pabbcc F paqbcc F paqbcc F paqbcc
F paqbcc F paqbcc F ppqbcc F ppqbcc
F p
→→ → → →→ → → →
→ → → →
→ 3 3 3
1 1 1 1
1 4 4 4
4 4 1
, $ , $ , $
, $ , $ , $ , $
, $ , $ , $ , $
, $ , $ , $
pqqcc F ppqqcc F ppqqcc F ppqqcc
F ppqqcc F ppqqcc F ppqqcc F ppqqcc
F ppqqcc F ppqqcc F ppqqcc F ppqqcc
F ppqqcc F ppqqcc G ppqqc
→ → →
→ → → →
→ → → →
→ → → 1
2 2 2 2
3 3 3 3
3 1 1 2
2
, $
, $ , $ , $ , $
, $ , $ , $ , $
, $ , $ , $ , $
, $
c G ppqqcc
G rpqqcc G rpqqcc G rpqqcc G rpqqcc
G rpqqsc G rpqqsc G rpqqsc G rpqqsc
G rpqqsc G rpqqsc G rpqqsc G rrqqsc
G rrqqsc
→
→ → → →
→ → → →
→ → → →
→ → 2 2 3
3 3 3 3
3 1 1 1
1 1 1 1
, $ , $ , $
, $ , $ , $ , $
, $ , $ , $ , $
, $ , $ , $ ,
G rrqqsc G rrqqsc G rrqqss
G rrqqss G rrqqss G rrqqss G rrqqss
G rrqqss G rrqqss G rrqqss G rrqqss
G rrqqss G rrqqss G rrqqss G
→ →
→ → → →
→ → → →
→ → → →
1 1 2 2
2 2 2 2 2
3
$ #
, $ , $ # , $ , $, $ , $ , $ , $ , $
, $ # , $ şirul este în limbaj.
rrqqss
C rrqqss C rrqqss C rrqqss C rrqqsC rrqq C rrq C rr C r C
C H Y
→ → → →→ → → → →
→ → −
5.3. CALCULE CU MAŞINI TURING
În exemplele 5.1. şi 5.2. am reconstruit maşini Turing care serveau
rolului de a recunoaşte diferite tipuri de limbaje. Maşina a decis dacă un
şir de intrare dat a fost „valid” sau nu, adică, au decideau dacă un şir dat
aparţinea unor limbaje anume. Maşinile Turing pot deservi şi rolul de
„calculator” sau „computer”. Mai precis, dacă presupunem că ( )f n este o
funcţie de o variabilă n care să fie un întreg pozitiv, şi presupunem că
valorile lui f sunt de asemenea întregi pozitivi ( :f + +→ ). Spunem că f
este calculabilă Turing dacă există o maşină Turing fT cu următoarea
proprietate: Pentru un input oarecare format din n de 1, maşina fT va
trece din configuraţia iniţială
0de ori 1
, $111 1n
Q K123
în configuraţia de oprire
de ( ) ori 1
, $ 111 1f n
H K123
Exemplu 5.3. Vom construi un exemplu de maşină Turing T
pentru funcţia ( ) 2f n n= . Practic, maşina va funcţiona în felul următor:
1. Pornind din cea mi din stânga celulă a benzii, maşina se deplasează
la dreapta până ce găseşte simbolul 1. Odată întâlnit, 1 este înlocuit
cu a iar capul continuă să se deplaseze spre dreapta până ce a
întâlnit şi înlocuit primul simbol blank # cu b.
2. Capul se întoarce la celula cea mai din stânga şi începe căutarea
unui alt 1. Odată găsit, acest 1 este din nou înlocuit cu a iar primul
simbol blank cu b.
3. Pasul 2 se repetă atâta timp cât mai sunt 1-uri în input-ul. De vreme
ce nu mai există 1-uri, banda va conţine n de a şi n de b. Toate
acestea sunt din nou înlocuite cu 1 iar maşina se opreşte.
Formal, această maşină este schiţată de diagrama din figura 5.6.
Starea 1Q este folosită pentru găsirea şi înlocuirea următorului 1 cu a, 2Q
găseşte primul # disponibil şi-l înlocuieşte cu b, 3Q mută capul înapoi pe
cea mai din stânga celulă, 4Q înlocuieşte a-urile şi b-urile cu 1-uri şi trece
în starea de oprire la apariţia lui $. Alfabetul benzii este {1, , , $, #}a bΣ = .
Simbolul $ este introdus aici, ca şi în exemplul anterior, pentru
simplificare – pentru a marca cea mai din stânga celulă a benzii dar poate
fi omis, ceea ce ar face maşina mai complicată. Considerăm, de pildă,
mişcările acestei maşini la input-ul 11σ = :
0 1 2 2
3 3 3 1
1 2 2 3
3 3 3 1
1 1
, $11 , $11 , $ 1 , $ 1#, $ 1 , $ 1 , $ 1 , $ 1, $ 1 , $ , $ # , $, $ , $ , $ , $, $ , $
Q Q Q a Q aQ a b Q a b Q a b Q a bQ a b Q aab Q aab Q aabbQ aabb Q aabb Q aabb Q aabbQ aabb Q aab
→ → →→ → → →→ → → →→ → → →
→ → 1 1
4 4 4 4
4
, $ , $ #, $ , $ 1 , $ 11 , $ 111, $1111 , $1111 O altă demonstraţie că 2*2 4.
b Q aabb Q aabbQ aabb Q aab Q aa Q aQ H
→ →→ → → →→ → − =
Figura 5.6. O maşină Turing care calculează.
Conceptul funcţiilor calculabile nu trebuie restrâns doar la funcţiile
întregi. O funcţie calculabilă pot fi văzută ca „algoritm” sau „set de
reguli”, care pentru un argument (input) dat, format dintr-un şir finit de
simboluri, produce o valoare (output), compusă la rândul ei dintr-un şir
finit de simboluri (potenţial diferite).
Definiţia 5.3. Fie 1∆ şi 2∆ două alfabete (mulţimi finite, nevide de
simboluri), care, pentru simplificare, presupunem că nu conţin
simbolurile $ şi #. Fie ( )f σ o funcţie a cărei argumente sunt şiruri σ de
simboluri din 1∆ şi ai cărei valori sunt şiruri ρ de simboluri din 2∆ .
Presupunem că f este definită pentru toate şirurile σ ca mai sus –* *1 2:f ∆ → ∆ . Spunem că f este calculabilă Turing dacă există o maşină
Turing fT astfel încât oricând ( )f σ ρ= , maşina fT va trece din
configuraţia iniţială 0 , $Q σ în configuraţia de oprire , $H ρ . Cu alte
cuvinte fT va transforma input-ul σ în output-ul ( )f σ .
Definiţia acoperă toate situaţiile posibile. De exemplu, o funcţie de
valori întregi cu trei variabile ( , , )w f x y z= este calculabilă Turing dacă
există o maşină Turing fT care va transforma un input-ul
{ { {1 2 3de ori de ori de ori
11 1| 11 1| 11 1x y z
e e eK K K
în
{de ( , , ) ori
11 1f x y z
e K
Acele e-uri pot fi şirul vid, +, sau – iar | este un separator. Aşadar, dacă
( , , ) 3 4w f x y z x y z= = − − , astfel ca (1,2, 3) 2f − = − , maşina Turing pentru f
are de transformat şirul 1|11| 111− în 11− , adică, trece din configuraţia
0 , $1|11| 111Q − în , $ 11H − .
Maşinile Turing sunt acceptate ca noţiuni precise a unor concepte
vagi de „algoritm” sau „procedură efectivă”. Astfel, a spune că există un
algoritm pentru rezolvarea unei probleme este echivalent cu a spune că
există o maşină Turing care, alimentată cu o bandă care conţine
descrierea acestei probleme, va executa o secvenţă finită de mişcări şi se
va opri cu banda conţinând soluţia problemei. Există alte definiri de
algoritmi şi funcţii efectiv calculabile, dar ele sunt echivalente cu cea dată
anterior. Afirmaţia că orice procedură efectiv calculabilă, sau orice
algoritm, poate fi implementat de o maşină Turing este cunoscută sub
numele de teză Church-Turing (vezi [6] şi [19]). Desigur nu poare fi
demonstrat, dar este aproape universal acceptat. Aceasta conduce în mod
natural la întrebarea dacă orice funcţie este calculabilă şi dacă orice
problemă are un algoritm care s-o rezolve. Mai exact prin aceasta se
înţelege următorul lucru:
1. Este adevărat că pentru o funcţie oarecare dată :f → , există o
maşină Turing fT care pentru orice n va executa următoarea secvenţă de
mişcări:
{ {*
0de ori 1 de ( ) ori 1
, $11 1 , $ 11 1n f n
Q H→K K
2. Întrebarea „Are fiecare problemă un algoritm care o va rezolva?”
este desigur prea vagă şi neprecisă pentru orice analiză matematică
raţională. O vom formula astfel: Presupus că C este o clasă de probleme,
fiecare din ea putând fi complet descrisă de un număr finit de simboluri
dintr-un alfabet fixat ∆ . În plus se presupune că fiecare problemă din C
este bine definită, adică, poate fi răspunsă cu Da sau Nu. A întreba de
existenţa unui algoritm pentru a rezolva toate problemele din C înseamnă
a întreba următoarele: Există o maşină Turing CT care pornită în
configuraţia 0 , $Q σ , unde σ este descrierea unei probleme din C, se va
opri în configuraţia , $H Y dacă răspunsul pentru σ este Da şi se va
opri în configuraţia , $H N dacă răspunsul pentru σ este Nu. Exprimat
în aceşti termeni, un algoritm este atunci doar o altă funcţie efectiv
calculabilă *: { , }f Y N∆ →
Surprinzător răspunsul la aceste două întrebări este nu. Există
funcţii necalculabile şi probleme nerezolvabile. Afirmaţia are, desigur, o
varietate de implicaţii filosofice, care însă nu vor fi atinse aici. În schimb,
restul capitolului va fi consacrat expunerii explicite a acestor probleme şi
funcţii.
5.4. EXTENSII ALE MAŞINILOR TURING
O proprietate curioasă, dar esenţială, a maşinilor Turing este că
puterea lor de calcul nu poate fi cu mult îmbunătăţită. Putem considera,
de pildă, maşini Turing cu mai multe benzi, definirea exactă fiind mai
mult sau mai puţin evidentă. Se descoperă că orice funcţie care poate fi
calculată de o astfel de maşină poate fi calculată şi de o maşină standard
(cu o bandă). Altă posibilitate este de a permite maşinii Turing să aibă
mai multe capuri de citire – din nou nu se obţine nimic prin aceasta. Tot
ce poate fi calculat de aceste maşini presupuse mai puternice poate fi
calculate şi de maşini Turing standard.
Situaţia este similară când considerăm maşini Turing
nedeterministe. Definiţia lor concretă este exact ca mai sus, cu excepţia
că funcţia de tranziţie ( , )Q xδ poate avea valori multiple: Dacă maşina se
află în starea Q iar capul ei punctează spre simbolul x de pe bandă atunci
( , )Q xδ dă lista mişcărilor legale posibile. Este dificil să vorbim de un
limbaj recunoscut de o maşină Turing nedeterministă, întrucât, în funcţie
de input-ul iniţial, alegeri diferit de mişcări pot duce la rezultate diferite.
Putem, însă, vorbi de un limbaj L acceptat de o maşină Turing
nedeterministă. Fiind dată o astfel de maşină Turing T, limbajul TL
acceptat de L se compune din acele şiruri σ pentru care există secvenţe
de mişcări legale, începând cu configuraţia 0 , $Q σ , care fac ca T să se
oprească. (Nu cerem ca T să poată decide dacă un şir dat σ este sau nu în
L.) Din punct de vedere a acceptării limbajelor, maşinile nedeterministe
nu sunt mai puternice decât cele deterministe: Dacă un limbaj L este
acceptat de o maşină Turing nedeterministă 1T , este acceptat şi de o altă
maşină Turing deterministă 2T . Astfel, situaţia este asemănătoare cu cazul
automatelor finite, dar diferită de automatele push-down.
Nu vom demonstra toate aceste rezultate – raţionamentele sunt
lungi şi nu conduc la o pătrundere mai adâncă în materia acestui subiect.
Cititorului îi este liber să aleagă o tratare mai detaliată al acestui subiect,
vezi [15] sau [8]. Vom da doar o singură ilustrare a unei teoreme de acest
gen, anume, că orice maşină Turing cu două benzi este echivalentă cu o
maşină standard cu o bandă. Mai precis, o maşină Turing cu două benzi
va avea şi două capuri. Aşadar funcţia de tranziţie δ a acestei maşini va fi
de forma
1 2 1 1 2 2ˆ ˆ ˆ( , , ) ( , , , , )Q x x Q x N x Nδ =
unde Q este starea curentă, 1x simbolul pe care se află capul de pe prima
bandă, 2x este simbolul citit de al doilea cap, Q este noua stare, 1x şi 2x
sunt simbolurile care înlocuiesc 1x şi 2x , iar 1N şi 2N sunt instrucţiunile
corespunzătoare pentru mutarea capurilor la dreapta ( iN R= ), stânga
( iN L= ) sau deloc ( iN S= ). O configuraţia a maşini va fi descrisă de
1 1 1 2 2 2, , Q x xα β α β
unde Q este starea curentă şi i i ixα β este conţinutul benzii i, 1, 2i = (locaţia
capului este marcată prin subliniere).
Figura 5.7. O maşină Turing cu două benzi.
De exemplu, maşina Turing cu două benzi din figura 5.7. se află în
configuraţia 7 , # , Q accb a abbacca . Dacă, 7 3( , , ) ( , , , , )Q c a Q b L b Rδ = ,
următoarea configuraţie a maşinii va fi 3, # , Q accb a bbbacca .
Fie L un limbaj peste un alfabet Σ . Spunem că L este recunoscut de
o maşină Turing cu două benzi 2T dacă pentru oricare σ din *Σ sunt
adevărate următoarele:
Lσ ∈ implică *
0 , $ , $ , $ , $Q H Yσ →
Starea curentă 7Q
Banda 2
Banda 1
Lσ ∉ implică *
0 , $ , $ , $ , $Q H Yσ →
Cu aceste notaţii avem:
Teorema 5.1. Fie L un limbaj peste un alfabet Σ . Atunci L este
recunoscut de o maşină Turing cu două benzi 2T dacă şi numai dacă este
recunoscut de o maşină standard cu o singură bandă 1T (definiţia 5.2.).
Demonstraţie. Dacă un limbaj este recunoscut de o maşină cu o
bandă 1T , este evident recunoscut şi de o maşină cu două benzi 2T : nu
mişcăm al doilea cap. Formal, dat fiind 1 0{Q, , , }T Q δ= Σ , maşina 2T va
avea aceleaşi stări şi acelaşi alfabet ca 1T , iar funcţia ei de tranziţie va fi
2 1ˆ ˆˆ( , , ) ( , , , , )Q x y Q x N y Sδ =
unde 1ˆ ˆˆ( , ) ( , , )Q x Q x Nδ = – mutăm primul cap din 2T în aceeaşi manieră ca
capul din 1T , iar al doilea cap îl lăsăm să puncteze întotdeauna spre celula
cea mai din dreapta. Partea dificilă (şi interesantă) a demonstraţiei este de
a arăta că dacă un limbaj L recunoscut de o maşină cu două benzi, este
recunoscut şi de o maşină standard cu o singură bandă. La prima vedere
se pare că având la dispoziţie o a doua bandă obţinem o mai mare putere
de calcul: Putem memora informaţie pe o bandă în timp ce lucrăm cu
cealaltă. Vom vedea că acesta nu este cazul. O demonstraţie formală
completă este grea, cu multe implicaţii şi oarecum dincolo de scopul
acestei lucrări. Vom prezenta o schiţă a ideii principale.
Fie 2T o maşină Turing cu două benzi care recunoaşte un limbaj L.
Notăm capurile cu 1h şi 2h . Vom construi mai întâi o maşină auxiliară cu
o bandă U care va simula mişcările lui 2T după cum urmează. Fiecare
celulă a benzii maşinii U va conţine: simbolul £, simbolul blank %
(pentru a-l putea deosebi de simbolul blank # al maşinii 2T ), sau un
cvadruplu 1 1 2 2( , , , )a aε ε . Simbolul se va afla întotdeauna în celula cea
mai din stânga şi nu va fi eliminat niciodată. Cvadruplul 1 1 2 2( , , , )a aε ε
din celula a i-a din U va conţine informaţia despre celulele i de pe benzile
maşinii 2T . (Indexarea celulelor din U începe de la 0: celula cea mai din
dreapta a lui U este celula 0, următoarea este prima celulă etc. Celulele
din 2T vor fi indexate începând cu 1: celula cea mai din stânga a fiecărei
benzi din 2T este referită ca celula numărul 1, urmată de celula numărul 2,
etc.)
Figura 5.8. O celulă a maşinii Turing U.
Dacă celulele i de pe benzile maşinii 2T conţine simbolurile x respectiv y,
atunci celula a i-a din U conţine cvadruplul 1 2( , , , )x yε ε . Simbolurile 1ε şi
2ε sunt determinate astfel: Dacă capul 1h punctează spre celula i a primei
benzi din 2T , punem 1 1ε = , în caz contrar 1 0ε = ; aceeaşi regulă se aplică
simbolului 2ε – este egal cu 1 sau 0 în funcţie dacă capul 2h punctează
spre celula a i-a a de pe banda a doua din 2T . Vom descrie un astfel de
cvadruplă în forma verticală ca în figura 5.8. Astfel, dacă benzile maşinii
2T se află în configuraţia din figura 5.9., banda maşini U va fi de forma
dată în figura 5.10.
Figura 5.9. Benzile unei maşini Turing cu două benzi.
Comportamentul maşinii U este acum evident: O singură mişcare a
maşinii 2T va rezulta în schimbarea stării maşinii, conţinutul a două celule
(câte una de pe fiecare bandă) şi reajustarea poziţiilor capurilor de citire
1h şi 2h . Fiecare astfel de mişcare a lui 2T va determină o secvenţă de
mişcări a lui U, rezultând într-o ajustare a celulelor sale – valorile
relevante pentru ia -uri şi iε se schimbă pentru a reflecta noua
configuraţie a maşinii 2T .
Figura 5.10. O bandă a unei maşini Turing.
Formal, alfabetul UΣ a maşinii U este dat de o mulţime finită
{£, %} ( {0, 1} {0, 1})UΣ = ∪ Σ× ×Σ×
Maşina U îşi va începe activitatea cu capul punctând pe celula cea mai
din stânga (conţinând simbolul £). După fiecare mişcare a lui 2T capul lui
se va deplasa la dreapta, făcând ajustările necesare, iar atunci se întoarce
Banda 1
Banda 2
Toţi # →
Toţi # →
Toţi % →
la cea mai din stânga celulă aşteptând următoarea mişcare a lui 2T .
Aceasta se poate realiza având stările din U ca expresii de forma
( , , , ( , , ))Q x y Q x yδ
unde Q este starea curentă din 2T iar x şi y sunt simbolurile din Σ care se
află sub capurile 1h respectiv 2h . Instrucţiunile maşinii U pot fi acum
explicitate:
1. Porneşte în starea 0 0 0 0 0 0( , , , ( , , ))Q x y Q x yδ cu capul punctând spre
celula cea mi din stânga (conţinând simbolul £). Simbolurile 0x şi
0y precum şi conţinutul iniţial al benzii din U vor reflecta
configuraţia iniţială a maşinii 2T .
2. Deplasează capul spre dreapta până ce sunt întâlnite ambele cazuri
de 1iε = . De fiecare dată, schimbă valorile a-urilor şi ε -urilor
relevante. (Informaţia privind ceea ce este de făcut dacă se
întâlneşte 1ε = este conţinută în valoarea funcţiei 0 0 0( , , )Q x yδ .)
Notează aceste valori, fie ele Q , x şi y ; se întoarce la celula cea
mai din stânga (care poate fi depistată prin prezenţa lui £); şi trece
într-o stare nouă ˆ ˆˆ ˆ ˆ ˆ( , , , ( , , ))Q x y Q x yδ .
3. Repetă pasul 2 până ce noua stare Q este starea de oprire H din 2T .
4. „Goleşte” prin a termina cu capul amplasat pe cea mai din stânga
celulă şi se opreşte.
Ca urmare, este evident că maşina cu o singură bandă U va simula
mişcările maşinii Turing cu două benzi 2T – orice decizie luată de 2T va fi
luată şi de U. De asemenea este limpede că, prin adăugarea unor stări
suplimentare la U, conţinutul final al benzii poate fi transformat în forma
cerută de enunţul teoremei 5.1. Q.E.D.
Trebuie remarcat faptul că adăugarea unei benzi suplimentare la o
maşină Turing nu are efect asupra puterii de calcul a acesteia, dar are
definitiv efect asupra eficienţei. Presupunem că 2T este o maşină Turing
cu două benzi simulată de o maşină Turing cu o singură bandă 1T , ca în
teorema 5.1. Dacă unul dintre capurile lui 2T este m celle îndepărtat de la
începutul benzii şi 2T face o mişcare, atunci 1T are de efectuat cel puţin m
mişcări pentru a simula această singură mişcare. Dacă 2T porneşte cu
ambele capuri pe cele mai din stânga celule şi la fiecare mişcare
amândouă capuri se deplasează la dreapta, atunci îi ia lui 1T cel puţin21
21 2 k k+ + + ≈L mişcări pentru a simula primele k mişcări ale lui 2T .
Aşadar, vag vorbind, dacă o maşină Turing necesită n mişcări pentru
rezolvarea unei anumite probleme, ne am putea aştepta ca adăugarea unei
benzi suplimentare va duce la rezolvarea problemei în n paşi. Această
idee poate fi cu mult precizată; studiul complexităţii de calcul se ocupă cu
întrebări de acest gen. Un cititor interesat poate consulta [13].
5.5. CODIFICĂRI
Evident că conceptul de maşină Turing este independent de modul
în care aceste maşini sunt descrise. Aşadar, nu contează dacă notăm
stările unui maşini cu 0Q , 1,Q K, sau 1P , 2 ,P K . Ceea ce contează sunt
„procesele interne” ale dispozitivului – adică, numărul de stări, numărul
de simboluri de bandă, relaţia de tranziţie şi desemnarea diferitelor stări
drept stări interne şi/sau de oprire. Vom prezenta acum o schemă care
descrie uniform oricare şi toate maşinile Turing. Mai exact, fiind dată o
maşină Turing T, vom arăta cum se dă o descriere completă şi neambiguă
a lui T utilizând doar un număr finit de simboluri fixate. De fapt, orice
maşină Turing poate fi descrisă folosind numai simbolurile B, A, E, P, X,
Y, L, R, S, 0 şi 1. Se procedează astfel: Prin definiţie, orice maşină Turing
se compune dintr-un număr finit de stări, un alfabet de bandă finit şi un
număr finit de relaţii de tranziţie care implică doar stările şi simbolurile
de bandă. Astfel, orice maşină Turing poate fi descrisă de o secvenţă de
simboluri
1 2 1 2 mB A PTT T Eε ε K (0.1)
unde
1. 1. 1ε este numărul de stări din T scris în notaţie binară (adică,
utilizând doar 0 şi 1). Starea iniţială are asociat numărul 1 şi starea
de oprire numărul 1ε .
2. 2. 2ε Este numărul de simboluri de bandă din T, din nou scris în
notaţie binară. Simbolul blank, care este un simbol de bandă pentru
oricare maşină Turing, va avea asociat numărul 1.
3. 3. 1 2, , , kT T TK sunt relaţii de tranziţie din T codificate în felul
următor. Fiecare stare şi fiecare simbol de bandă din T are asociat
un număr unic – stările au numere între 1 şi 1ε iar simbolurile de
bandă numere între 1 şi 2ε . Fiecare relaţie de tranziţie
ˆ ˆ( , ) ( , , )Q x Q x Nδ = este atunci codificată ca
1 2 3 4X X X XNYη η η η
unde 1η şi 2η sunt numerele asociate lui Q şi x, respectiv 3η şi 4η
sunt numerele asociat lui Q şi x iar , sau N R L S= . Simbolurile B,
A, P, X, Y şi E sunt folosite drept delimitatoare.
Dacă T este o maşină Turing, notăm cu 1( )D T descrierea lui T dată
de (5.1) este:
1 1 2 1 2( ) mD T B A PTT T Eε ε= K (0.2)
Similar, orice segment iniţial (finit) de bandă a unei maşini Turing
T poate fi codificară utilizând doar simbolurile A, F, W, Z, 0 şi 1.
Codificarea unei astfel de benzi are forma
2 1 2 2 kW A Z Z Z Fε ψ ψ ψ ψK (0.3)
Aici 2ε este numărul de simboluri de bandă din T şi 1 2, , , kψ ψ ψK sunt
numerele acestor simboluri care apar efectiv pe bandă: 1ψ este numărul
simbolului de bandă din prima (cea mai din stânga) celulă, 2ψ este
numărul simbolului din a doua celulă, etc. Aceste numere
2 1 2, , , , kε η η ηK sunt exprimate în notaţie binară iar W, A, Z şi F servesc
drept delimitatori. Se subînţelege că simbolul din dreapta celulei k este
simbolul blank, a cărui număr este 1. Codificarea părţii iniţiale σ a benzii
descrise va fi notat 2 ( )D σ :
2 2 1 2 2( ) kD W A Z Z Z Fσ ε ψ ψ ψ ψ= K (0.4)
Exemplu 5.4. Considerăm maşina Turing dată de diagrama din
figura 5.11.
Figura 5.11. O maşină Turing T.
Această maşină are trei stări, deci 1 11ε = (binar, 3 în decimal). Prin
convenţie, starea iniţială are asociat numărul 1 iar starea de oprire H
numărul 1 11ε = ; aşadar, 1Q are asociat numărul 10. Mai are 4 simboluri de
bandă: a, b, c şi #, deci 2 100ε = (în binar); prin convenţie # are asociat
numărul 1 iar noi asociem 10 lui a, 11 lui b şi 100 lui c. Tranziţiile lui T
sunt codificate astfel:
{ { { {0 0
1 10 1 10 Q Qa a
X X X X R Y
{ { { {0 1 #
1 11 10 1 Q b Q
X X X X S Y
reprezintă 1 1( , ) ( , , )Q b Q b Rδ = şi este codificat ca
reprezintă 0 0( , ) ( , , )Q a Q a Rδ = şi se codifică ca
reprezintă 0 1( , ) ( , #, )Q b Q Sδ = şi este codificat ca
{ { { {1 1
10 11 10 11 b bQ Q
X X X X R Y
{ { { {1
10 10 11 100 HQ a c
X X X X R Y
Codificarea întregii maşini Turing este atunci
{ {1 2 1 2
3 4
1( ) 11 100 1 10 1 10 1 11 10 1
10 11 10 11 10 10 11 100 T T
T T
D T B A P X X X XRY X X X XSY
X X X XRY X X X XRY Eε ε
= 144424443 144424443
144424443 144424443
Similar, dacă partea stângă a benzii lui T ar fi #ab acσ = , conţinutul
benzii s-ar codifica astfel:
{ { { { { {2
2#
( ) 100 10 11 1 10 100 ba a c
D W A Z Z Z Z Fε
σ =
Din acest exemplu se observă că maşini mai complexe vor avea
codificări considerabil mai lungi, dar în principiu, orice maşină Turing şi
orice parte finită a benzii poate fi codificată cu această schemă.
Posibilitatea codificării complete şi neambigue a unei maşini
Turing arbitrare şi a input-ului ei ne permite să construim aşa numita
maşină Turing universală 0U . În esenţă, o astfel de maşină simulează
orice altă maşină Turing în felul următor: Fie T o maşină Turing oarecare
şi fie σ conţinutul iniţial al benzii lui T. Fie 1( )D T şi 2 ( )D σ codificările
pentru T şi σ descrise mai sus. Punem maşina T în configuraţia iniţială
0 , Q σ şi maşina 0U în configuraţia 0 1 2, ( )$ ( )Q D T D σ . Cu alte cuvinte,
reprezintă 1( , ) ( , , )Q a H c Rδ = şi este codificat ca
introducem descrierea lui T şi conţinutul iniţial σ al benzii din T în
maşina 0U . „Universalitatea” lui 0U se bazează pe următoarea descriere a
comportamentului ei:
1. Dacă, pornind din configuraţia iniţială 0 , Q σ , T se opreşte
având ca conţinut al benzii şirul τ , atunci 0U , pornind din configuraţia
0 1 2, ( )$ ( )Q D T D σ , se va opri de asemenea, cu banda conţinând şirul
2 ( )D τ . Formal,
*
0 , , Q Hσ τ→ implică *
0 1 2 2, ( )$ ( ) , D ( )Q D T D Hσ τ→
Poziţia exactă a capurilor celor două maşini este neesenţială.
2. Dacă T nu se opreşte cu input-ul indicat, nu se va opri nici 0U .
Construcţia formală exactă a maşinii 0U este greoaie, lungă şi
oarecum dincolo de scopul acestei lucrări. Vom prezenta doar ideea
principală; pentru detalii suplimentare cititorul este invitat să consulte
[13]. Maşina Turing universală 0U va avea trei benzi T1, T2 şi T3 cu
capurile corespunzătoare 1h , 2h şi 3h . Banda T1 va conţine descrierea
codificată a maşinii Turing T simulate şi banda T2 va conţine input-ul
iniţial al lui T. Banda T3 va conţine starea curentă şi locaţia curentă a
capului maşinii T. Instrucţiunile maşinii 0U sunt următoarele:
1. Introduce codificarea 1( )D T a maşinii T pe banda T1, codificarea
2 ( )D σ a inputului iniţial σ pentru T pe banda T2 şi starea iniţială a
lui T împreună cu poziţia capului lui T pe banda T3. Poziţionează
toate capurile 1h , 2h şi 3h la capătul stâng al benzilor
corespunzătoare.
2. Deplasează capul 3h spre dreapta până ce s-a găsite descrierea stării
curente şi locaţia curentă a capului din T.
3. Utilizând informaţiile obţinute la pasul 2, deplasează capul 1h până
ce s-a găsit descrierea corespunzătoarea a funcţie de tranziţie δ .
4. Utilizând informaţiile din paşii 1 şi 2, ajustează conţinutul benzilor
T1 şi T2 pentru a reflecta noua stare şi noua bandă a lui T.
5. Dacă noua stare a lui T este starea de oprire atunci „goleşte” dacă
nu deplasează toate capurile de citire pe cea mai din stânga celulă
şi continuă cu pasul 2.
Faptul că 0U are trei stări nu ridică probleme; conform teoremei
5.1, ea poate fi acum înlocuită de o maşină Turing standard cu o singură
bandă. Această idee se formalizează în felul următor.
Definiţia 5.4. O maşină Turing 00 0{Q, , , }U Q δ= Σ se numeşte
universală dacă are următoarea proprietate. Fie 0 0{Q, , , }T Q δ= Σ o maşină
Turing oarecare şi fie σ un şir din *Σ . Fie 1( )D T codificare lui T şi 2 ( )D σ
codificarea lui σ . Maşina T va executa secvenţa de mişcări*
0 , , Q Hσ τ→ dacă şi numai dacă maşina 0U execută secvenţa de
mişcări
*
0 1 2 2, ( )$ ( ) , D ( )Q D T D Hσ τ→
Se presupune că maşinile de mai sus încep şi încetează activitatea cu
capul amplasat pe cea mai din stânga celulă.
Teorema 5.2. Există o maşină Turing universală.
Remarcăm faptul că există o maşină Turing universală cu numai
două stări. Construcţia ei a fost dată de C. E. Shannon în [18].
Posibilitate codificării oricărei maşini Turing are o altă consecinţă
importantă: Este posibilă listarea maşinilor într-o singură secvenţă
1 2 3 4, , , , T T T T K (0.5)
Orice maşină Turing posibilă se va afla pe undeva în această listă.
Enumerare de maşini Turing se realizează astfel: Am văzut că o maşină
Turing poate fi unic descrisă de o secvenţă finită de simboluri, fiecare
dintre ele fiind unul din cele 11 caractere: B, A, E, P, X, Y, R, L, S, 0 şi 1.
Pentru un întreg oarecare n, există doar un număr finit de şiruri de
lungime n – de fapt sunt exact 11n . Aşadar, putem lista toate maşinile
Turing într-o secvenţă astfel: Mai întâi listăm toate maşinile Turing a
căror descriere necesită doar un singur simbol (dacă există), atunci toate
maşinile descrise de 2 simboluri (dacă există), etc. Cea mai „mică”
maşină Turing este
care are doar un singur simbol de bandă #. (Acesta este minimul ce poate
avea o maşină Turing.) Descrierea este 10 1B A PE , necesitând un şir de
lungime 7 şi stă la începutul secvenţei (5.5). Aşadar avem următoarele:
Teorema 5.3. Numărul de maşini Turing distincte este numerabil.
În exact acelaşi mod, toate input-urile posibile a tuturor maşinilor
Turing pot fi ordonate într-o singură secvenţă. Aceasta rezultă din faptul
că orice porţiune finită a unei benzii poate fi descrisă utilizând doar un şir
finit de simboluri A, W, Z, F, 0 şi 1. Restul raţionamentului rămâne la fel.
5.6. PROBLEME DE DECIDABILITATE
În acest paragraf vom da o formulare precisă (şi soluţia) problemei
discutate pe scurt în paragraful 5.3.
1. Are fiecare problemă un algoritm care o rezolvă?
2. Este fiecare funcţie calculabilă?
Aceste două întrebări sunt de fapt identice, întrucât „soluţia problemei”
poate fi văzută ca funcţie a descrierii problemei. A demonstra numai că
există funcţii necalculabile este uşor. Din teorema 5.3. avem că există
doar numerabil de multe maşini Turing. Există nenumerabile funcţii
: {0,1}f → , vezi Appendix 1. Aşadar unele dintre aceste funcţii (de fapt,
majoritatea lor) nu vor fi calculabile Turing. Acest argument, deşi perfect
corect, este oarecum nesatisfăcător, întrucât nu dă un exemplu specific de
problemă nerezolvabilă sau funcţie necalculabilă. Vom da în acest
paragraf două exemple concrete de acest tip.
Ne întoarcem la întrebarea existenţei unui algoritm pentru
rezolvarea unei probleme date. Reamintim că a spune că există un
algoritm de rezolvare a unei probleme este identic cu a spune că există o
maşină Turing care va rezolva aceea problemă (teza lui Church-Turing).
Vom arăta că nu există un algoritm care, dacă este dată descrierea unei
maşini Turing T şi descrierea inputului σ pentru T, va determina dacă T
se opreşte sau nu. Aşadar, spunem că problema execuţiei maşinii Turing
este nedecidabilă. În termenii maşinii Turing aceasta poate fi formulat în
felul următor:
Teorema 5.4. Problema execuţiei pentru maşini Turing este
nedecidabilă. Mai precis, nu există o maşină Turing 0 0{Q, , , }A Q δ= Σ cu
următoarele proprietăţi: Fie 0 0ˆ ˆ ˆˆ{Q, , , }T Q δ= Σ o maşină Turing oarecare şi
fie σ un şir oarecare din *Σ , şi 1( )D T , 2 ( )D σ codificarea lui T respectiv
σ , descrisă în paragraful 5.4. Considerăm comportamentul lui T la
input-ul σ (adică, comportamentul lui T pornit în configuraţia 0ˆ , Q σ , cu
capul punctând spre cea mai din stânga celulă). Mai considerăm
comportamentul lui A la input-ul 1 2$ ( )£ ( )D T D σ , adică, comportamentul lui
A pornit în configuraţia iniţială 0 1 2, $ ( )£ ( )Q D T D σ . Dacă T se opreşte,
eventual, atunci A se va opri în configuraţia , 1H , dacă T nu se opreşte
atunci A se va opri în configuraţia , 0H .
Remarcăm că T nu trebuie să se oprească – poate intra într-un ciclu
infinit sau se poate bloca; maşina A trebuie să se oprească întotdeauna, cu
condiţia că a primit un input corect format. Pentru a demonstra teorema
avem nevoie de unele rezultate preliminare. Fie 1 2 3, , , T T T K enumerarea
tuturor maşinilor Turing şi fie 1 2 3, , , σ σ σ K secvenţa tuturor input-urilor
admise pe această maşină. T-urile şi σ -urile sunt codificate ca în
paragraful 5.5. Fie 0L mulţimea acelor iσ pentru care maşina iT nu se
opreşte în configuraţia , 1H . Aşadar, o secvenţă de input iσ este în
limbajul 0L dacă şi numai dacă maşina iT , pornită în configuraţia( )0 , i
iQ σ , nu se opreşte deloc sau se opreşte într-o altă configuraţie decât
, 1H .
Lema 5.1. Nu există nici o maşină Turing 0T care va decide pentru
fiecare iσ dacă iσ aparţine, sau nu, limbajului 0L . Mai precis, nu există
nici o maşină Turing 0 0 0 0 0{Q , , , }T Q δ= Σ cu proprietatea ca pentru fiecare
1,2,3,i = K
1. *
0 , $ , 1iQ Hσ → dacă iσ este în 0L
2. *
0 , $ , 0iQ Hσ → dacă iσ nu este în 0L
Demonstraţie. Presupunem că o asemenea maşină 0T există; atunci
va trebui să fie una dintre 1 2, , T T K din (5.5.). Fie atunci 00 iT T= şi să
vedem ce se întâmplă dacă pornim 00 iT T= cu input-ul
0iσ . Din ipoteză,
00 ( )iT T= ea se va opri sau în configuraţia , 1H sau în , 0H . În primul
caz, 0i
σ este în limbajul 0L , ceea ce înseamnă că 0i
T nu se opreşte în
configuraţia , 1H ; evident, este imposibil. Dacă 00 iT T= se opreşte în
configuraţia , 0 , 1H H≠ , înseamnă că 0i
σ este în limbajul 0L , aşadar
0T – şi deci 0i
T – ar trebui să se oprească în configuraţia , 1H , dar am
presupus că aceasta nu are loc. Ca urmare, 0T nu poate decide cu
exactitate dacă 0i
σ aparţine limbajului 0L . Q.E.D.
Putem demonstra acum teorema 5.4. Ideea demonstraţiei este de a
arăta că dacă o maşină Turing A, descrisă în teorema 5.4., există, atunci se
poate construi o maşină 0T care recunoaşte limbajul 0L ca în lema 5.1.
Ceea ce este însă imposibil. Presupunând că A există, construcţia lui 0T
este următoarea: Fiind dat un şir iσ , maşina 0T trimite codificarea 2 ( )iD σ
şi 1( )iD T la maşina A. Dacă A se opreşte cu „0” pe banda (în configuraţia
, 0H ), atunci 0T scrie 1 pe bandă şi se opreşte în configuraţia , 1H .
(S-ar putea să aibă de făcut unele operaţii de golire.) Dacă A se opreşte cu
1 pe bandă (în configuraţia , 1H ), atunci 0T trimite descrierile 1( )iD T şi
2 ( )iD σ la maşina universală 0U din teorema 5.2. Prin definiţie, maşina 0U
se va comporta la acest input în acelaşi mod ca maşina iT cu input-ul iσ ,
adică se va opri. (Întrucât A a anticipat, probabil corect, că iT se va opri.)
Dacă U se opreşte cu 1 pe banda sa, 0T va scrie 0 pe bandă şi se opreşte în
configuraţia , 0H . Dacă U se opreşte cu banda conţinând alt ceva decât
1, atunci 0T va scrie 1 pe banda sa şi se opreşte în configuraţia , 1H .
Este acum simplu de arătat că maşina 0T va anticipa corect dacă un şir iσ
dat este în limbajul 0L sau nu. Presupunem că iσ este în limbajul 0L .
Aceasta înseamnă că iT , la input-ul iσ , nu se va opri în configuraţia
, 1H . Există două posibilităţi: i) iT nu se va opri deloc, sau ii) iT se va
opri, dar într-o altă configuraţie decât , 1H . În cazul i), maşina A se va
opri în configuraţia , 0H deci, prin construcţie, 0T se va opri în
configuraţia , 1H , anticipând corect că 0i Lσ ∈ . În cazul ii), A se va opri
în configuraţia , 1H , iar şirul iσ , împreună cu descrierea lui iT vor fi
introduse în maşina universală 0U , care, la rândul ei, se opreşte într-o
configuraţie diferite de , 1H . Din nou, prin construcţie, 0T se va opri în
configuraţia , 1H , anticipând corect că 0i Lσ ∈ . De asemenea se vede
uşor că 0T se va comporta corect dacă 0i Lσ ∉ , lăsăm demonstraţia ca
exerciţiu. Q.E.D.
Ne îndreptăm acum atenţia spre funcţii necalculabile. Reamintim
că o funcţie ( )f n m= (n, m numere pozitive) se numeşte calculabilă dacă
există o maşină Turing fT care, la input-ul $111 1K (de n ori 1) va produce
ca output $111 1K (de ( )f n ori 1). O funcţie f care nu este calculabilă se
numeşte necalculabilă.
Teorema 5.5. Există o funcţie necalculabilă.
Demonstraţie. Am văzut în paragraful 5.5. că există o mulţime
finită 1∆ astfel încât orice maşină Turing poate fi descrisă de un şir finit
de elemente (caractere) din 1∆ . De fapt, această mulţime poate fi formată
din 11 caractere distincte. În mod similar, orice input pentru o maşină
Turing poate fi descris de un şir finit de simboluri dintr-o mulţime 2∆ ,
unde 2∆ este din nou finită. (În paragraful 5.5. mulţime 2∆ are şase
elemente.) Fie T o maşină Turing şi fie σ un input pentru T (adică,
conţinutul iniţial al benzii lui T). Fie 1( )D T şi 2 ( )D σ descrierile lui T
respectiv σ . Fie ( )p T lungimea şirului 1( )D T şie fie ( )q σ lungimea
şirului σ . Pentru un întreg pozitiv n, există doar un număr finit de perechi
( , )T σ , unde T este o maşină Turing iar σ este input-ul ei iniţial, astfel ca
( ) ( )p T q nσ+ ≤ . Fie nA mulţimea acestor perechi. Dacă ( , )T σ este o
pereche din nA , atunci T, cu input-ul σ , se poate opri sau nu. Fie nB
mulţimea acelor perechi din nA care au proprietatea ca T să se oprească la
input-ul σ . Din nou, nB se compune dintr-un număr finit de perechi.
Dacă ( , )T σ este o pereche din nB , fie ( , )Tβ σ desemnând numărul de
mişcări pe care T le face înaintea de a se opri în configuraţia de oprire.
Definim acum o funcţia ( )b n
( ) { ( , ) | ( , ) }nb n Max T Tβ σ σ= ∈B
În general, ( )b n este cel mai mare număr de mişcări pe care o maşină
Turing îl poate executa asupra unui input σ , dacă descrierea lui T şi σ
luate împreună nu depăşesc n simboluri. Funcţia ( )b n astfel definită se
numeşte funcţie busy beaver şi nu este necalculabilă. Presupunem că
există o maşină Turing B care calculează ( )b n . Vom arăta că această
implică că se poate construi o maşină Turing A care rezolvă problema.
Aceasta, însă este imposibil, după cum arată teorema 5.4. Pentru a
construi A procedăm astfel: Fiind dată o maşină Turing şi T cu inputul σ ,
maşina A codifică T şi σ ca 1( )D T şi 2 ( )D σ şi calculează ( ) ( )n p T q σ= + .
După aceasta, A pasează acest număr n maşinii B şi obţine ( )b n . Având
acestea făcute, pasează descrierile 1( )D T şi 2 ( )D σ , ale lui T şi σ , la
maşina universală 0U şi începe să numere mişcările lui 0U . Dacă 0U se
opreşte înainte de ( )b n mişcări, A scrie 1 pe banda ei şi se opreşte în
configuraţia , 1H . Dacă 0U nu se opreşte la a ( )b n -a mişcarea, A scrie 0
pe bandă şi se opreşte în configuraţia , 0H . Este limpede că A se va
comporta corect: Dacă 0U nu se opreşte la a ( )b n -a mişcarea, nu o va face
nici T, întrucât 0U simulează pe T mişcare cu mişcare şi ( ) ( )p T q nσ+ ≤ .
Q.E.D.
Merită făcute unele comentarii asupra ultimelor două teoreme.
Dacă teorema 5.4. afirmă că problema de oprire a maşinilor Turing este
nedecidabilă, nu înseamnă că nu putem decide, în unele cazuri specifice,
dacă o maşină Turing dată se va opri, sau nu, la un input fixat.
Considerăm, de pildă, maşina Turing descrisă în figura 5.12. Se observă
că dacă maşina T este pornită în configuraţia 0 , Q ab nu se va opri
niciodată; dacă însă este pornită în configuraţia 0 , Q baab se va opri.
Ceea ce afirmă teorema este că nu există o metodă universală care va
decide această întrebare în toate cazurile posibile.
Figura 5.12. O maşină Turing care în unele cazuri se opreşte iar în altele
nu.
Multe dintre întrebările legate de limbaje formale sunt
nedecidabile. Vom enumera aici câteva dintre ele. A le demonstra ne ar
duce însă prea departe. Cititorul interesat este invitat să consule unele
tratate excelente referitoare la acest subiect, de exemplu, [13] sau [15].
Teorema 5.6. Este nedecidabil dacă o gramatică independentă de
context arbitrară este ambiguă.
Din nou, aceasta nu înseamnă că în unele cazuri speciale nu putem
decide această problemă. O gramatică | |S a b λ→ este evident
neambiguă. Ceea ce afirmă teorema este că nu există o maşină Turing
care, la un input dat ce descrie o gramatică, decide dacă această gramatică
este ambiguă sau nu. Evident că este posibil să descriem o gramatică
printr-o secvenţă finită de simboluri, deci punerea problema existenţei
unei astfel de maşini Turing are sens.
Teorema 5.7. Este nedecidabil dacă două gramatici independente
de context au o propoziţie comună.
Aşadar, nu există o maşină Turing care, pentru două gramatici
independente de context 1G şi 2G date, va decide dacă 1 2( ) ( )L G L G∩ =∅ .
Vom arăta în capitolul 6, că există o procedură, adică, o maşină Turing,
care, primind o gramatică independentă de context { , , , }G N S P= Σ şi un
şir specific σ din *Σ , va decide dacă ( )L Gσ ∈ sau nu.
Teorema 5.8. Este nedecidabil dacă o gramatică independentă de
context arbitrară este ambiguă în mod inerent.
Chiar mai surprinzător avem:
Teorema 5.9. Este nedecidabil dacă o gramatică independentă de
context arbitrară are o gramatică regulară.
PROBLEME
1. Construiţi o maşină Turing care recunoaşte limbajul2{1 | 0,1, 2, }nL n= = K Arătaţi mişcările maşinii cu input-urle 111 şi
1111.
2. Construiţi o maşină Turing care va calcula funcţia ( ) 3f n n= .
Arătaţi mişcările maşinii cu input-ul 11.
3. Fie următoarea maşină Turing dată sub formă tabelară
Simbol de intrare
a b c #
0Q 1( , , )Q a S 1( , , )Q b S ( , , )H c S 0( , #, )Q R
1Q 1( , , )Q b R 1( , , )Q a R 2( , , )Q c S 2( , #, )Q S
S
t
a
r
e2Q 2( , , )Q a L 2( , , )Q b L 2( , , )Q c L ( , #, )H S
a. Arătaţi mişcările acestei maşini începând din configuraţiile
0 , #Q abbaacaa , 0 , #Q bbaaca şi 0 , #Q abbcaab .
b. Daţi o diagramă de stare a maşinii.
c. Descrieţi neformal ce face maşina.
4. Fie următoarea maşină Turing
a. Arătaţi mişcările maşinii la input-ul ababbbaσ = începând cu
configuraţia 0 , Q ababbba .
b. Daţi o descriere tabelară a maşinii.
c. Descrieţi neformal ce face maşina.
5. Consideraţi o maşină Turing care compară două numere m şi n.
Maşina ar trebui să treacă din configuraţia
{{0 , #11 1#11 1n m
Q K K în , #H x ,
unde , sau x f s e= în funcţie dacă n m> , n m< sau n m= .
6. Construiţi o maşină Turing cu o bandă infinită bidirecţională car se
va opri dacă şi numai dacă input-ul iniţial conţine simbolul a.
Acest simbol poate apărea oriunde pe bandă, nu neapărat în dreapta
poziţiei iniţiale a capului.
7. Construiţi o maşină Turing care recunoaşte limbajul*{ | { , } }RL a bσσ σ= ∈ . Aici, Rσ desemnează inversul şirului σ .
8. Daţi codificări ale maşinilor Turing din problemele 1 şi 2, conform
descrierii din paragraful 5.5. De asemenea daţi codificarea
conţinutului iniţial al benzii din configuraţia iniţială menţionată în
aceste probleme.
9. Demonstraţi că nu există un algoritm care decide dacă o maşină
Turing cu input iniţial dat se va întoarce cândva în starea iniţială
0Q .
10. Demonstraţi că nu există un algoritm care decide dacă o maşină
Turing cu input iniţial dat va scrie cândva simbolul a pe bandă.