-
CAPITOLUL 5
MAINI TURING
5.1. INTRODUCERE I DEFINIII
n capitolele precedente am introdus diferite tipuri de dispozitive
automate, cum sunt mainile cu stri finite i automatele push-down, care
sunt menite s recunoasc limbaje generate de gramatici. Numrul
tipurilor de limbaje recunoscute de automatele finite a fost foarte restrns
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
mainile 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 maini cu output (paragrafele 3.4. i 4.3). Ele pot fi
vzute ca modele matematice a unui concept de algoritm intuitiv: Pentru
un input dat (sub forma unui ir finit de simboluri pe o band), maina
opereaz asupra acestui input i produce diferite output-uri. Procesul de
calcul n aceste maini const n schimbarea strilor interne i
modificarea diferiilor pointeri (input, stiv i/sau output). n acest capitol
vom studia un alt dispozitiv, numit main Turing, care nglobeaz toate
aceste caracteristici, i este mai puternic dect toate mainile discutate
pn acuma. Mainile Turing par a fi cele mai puternice dispozitive
automate posibile ele sunt n esen definiia 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 trziu, dar
n esen avem urmtoarea situaie.
Un algoritm poate fi vzut ca o mulime de instruciuni, sau dac
dorim ca o carte de bucate, folosit de o main care va aciona asupra
-
diferitelor tipuri de input-uri. Input-urile pot fi vzute ca o mulime finit
de simboluri care urmeaz a fi citite de o main (unul cte unul), i
programul sau instruciunile care arat mainii ce are de fcut dup citirea
fiecrui astfel de simbol. n esen, acesta este comportamentul mainilor
Turing, ns partea interesant este faptul c orice definire rezonabil,
precis a unui algoritm este echivalent cu conceptul de main Turing.
Pe de alt parte, un algoritm este definit ca o main Turing.
n esen, o main Turing este compus dintr-un numr finit de
stri i o band. Banda este mprit ntr-un numr infinit (numerabil) de
celule i este infinit la dreapta. Mainile Turing pot fi reprezentate ca n
figura 5.1.
Figura 5.1. O main Turing.
Maina 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
mulime 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 numete 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 numr finit de
celule care conin un simbol ne-blank, toate celelalte celule sunt blank.
Aadar, toate celulele din dreapta unei celule sunt blank. Maina opereaz
n pai discrei. La orice moment dat se afl ntr-o stare Q iar capul ei de
citire puncteaz spre o celul care conine un simbol x . Pe baza
acestor informaii i numai acestora, maina efectueaz urmtoarele trei
operaii:
1. Trece ntr-o stare nou Q .
2. nlocuiete simbolul x, scanat anterior de capul de citire, cu alt
simbol x din .
3. Mut capul cu o celul la dreapta sau la stnga, sau deloc.
Aceste trei aciuni, executate mpreun, se numesc micare. Dup
efectuarea unei micri maina se afl ntr-o alt stare i citete alt
simbol, deci execut alt micare iar procedeul se repet. Iniial, maina
se afl ntr-o stare iniial special, pe care de obicei o vom nota 0Q iar
banda este umplut cu secvene de simboluri din . Coninutul iniial al
benzii va fi numit input. Vom presupune ntotdeauna c input-ul conine
doar un numr finit de celule ne-blank. Aadar, cu aceste setri iniiale,
maina intr n execuie. Ea se va opri n urmtoarele trei situaii:
1. Una din strile mainii este desemnat ca stare de oprire i va fi
ntotdeauna notat cu H. Dup ce maina intr n aceast stare H ea se
oprete i-i termin activitate. Spunem n acest caz c maina s-a oprit.
2. Capul de citire/scriere puncteaz spre cea mai din stnga celul
de pe band i instruciunile cer capului s se deplaseze cu o celul la
-
dreapta. n aceast situaie maina nceteaz s opereze; vom spune c
maina s-a blocat.
3. Pentru starea curent i simbolul pe care se afl poziionat capul
nu exist instruciuni n programul mainii. Dac aceasta are loc, spunem
de asemenea c maina s-a blocat.
Aadar, fiind dar un input-ul iniial, maina ncepe n starea iniial
0Q i trece prin stri n timp ce opereaz asupra benzii de intrare. Ea poate
aciona nedefinit, se poate opri sau se poate bloca. Formal avem:
Definiia 5.1. O main Turing T se compune din urmtoarele
patru obiecte:
1. O mulime finit de stri Q. Unul dintre elementele din Q este
denotat prin H i se numete starea de oprire.
2. O mulime 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 aparin lui .
3. O stare specificat 0Q din Q numit stare iniial.
4. O funcie de tranziie ( , )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 funcia nu trebuie s fie definit pentru toate
valorile de Q i x.
O astfel de main Turing se noteaz 0{ , , , }T Q Q = . Funcia de
tranziie ( , ) ( , , )Q x Q x N = se interpreteaz astfel: Dac maina se afl n
starea Q i capul ei de citire/scriere puncteaz la simbolul x, atunci T trece
n starea Q , nlocuiete x cu x i deplaseaz capul cu o celul spre
dreapta ( N R= ), o celul spre stnga (dac N I= ) sau rmne neschimbat
(dac N S= ).
nainte de a prezenta un exemplu, vom elabora o notaie pentru
descrierea configuraiilor mainilor Turing. ntruct n orice moment dat
banda mainii conine doar un numr finit de simboluri ne-blank,
coninutul unei astfel de benzi este descris complet prin listarea prii
stngi a benzii inclusiv ultimul simbol ne-blank. Pentru evitarea unor
ambiguiti de pild, cnd banda este complet goal descriem
coninutul benzii cu trei simboluri: 1 , x i 2 , unde 1 este coninutul
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 stnga celul a benzii, dac 2 = , toate celulele
din dreapta capului sunt blank (adic, conin simbolul #). Configuraia
unei maini 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, configuraiile (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 combinm irurile 1 , x i 2 ntr-un singur
ir 1 2x i s subliniem poziia capului (adic, simbolul x). Aadar,
1 2, , , Q x este scris ca 1 2, , , Q x . Configuraiile din figura 5.2.
-
vor fi atunci 4 , # #Q a ba a i 5 , #Q aba . Configuraia unei maini ntr-o
stare Q, cu banda complet goal i cu capul punctnd spre celula cea mai
din stnga este atunci , #Q .
Figura 5.2. Configuraia unei maini Turing.
Presupunem acum c maina Turing se afl n configuraia
1 2, Q x i n urma aplicrii unei funcii de tranziie trece n
configuraia 1 2 , Q x . Notm aceasta
1 2 1 2 , , Q x Q x
Dac maina T trece din configuraia 1 2, Q x n 1 2 , Q x printr-o
secven de mai multe micri, notm aceasta
*
1 2 1 2 , , Q x Q x
Notaia aceasta este complet analoag cu cea folosit la descrierea
micrilor unei maini cu stri finite sau automat push-down. n aceeai
manier, mainile Turing pot fi reprezentate prin diagrame similare celor
ale mainilor cu stri finite. Dac 0{Q, , , }T Q = este o main Turing,
(i) (ii)
-
pentru fiecare valoare ( , ) ( , , )Q x Q x N = desenm o sgeat ntre strile Q
i Q , ca n figura 5.3.
Figura 5.3. Tranziia unei maini Turing.
5.2. MAINI TURING CA PROCEDURI DE DECIZIE
Mainile Turing pot fi utilizate ca acceptori de limbaje. Prin
aceasta nelegem c o main Turing LT T= recunoate un limbaj L dat,
dac T poate determina dac un ir este n L sau nu. O astfel de main
Turing este vzut ca o procedur de decizie de apartenen la un
limbaj. Aceasta este analog cazului mainilor cu stri finite. Caz n care,
dat fiind un limbaj L i o MSF M care recunoate L, am putut determina
pentru orice ir dac aparine sau nu lui L. Procedura era simpl: Am
pornit M n starea iniial 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 mainilor Turing,
informaia dac un ir dat aparine sau nu limbajului, este afiat pe band.
Formal avem urmtoarele.
Definiia 5.2. Presupunem c L este un limbaj peste un alfabet ;
pentru simplificare presupunem c nu conine simbolurile # i $.
Spunem c L este recunoscut n sens Turing, dac exist o main Turing
LT T= cu urmtoarele proprieti:
unde , sau N L R S=
-
1. Alfabetul de band a lui T conine { , #}S (poate conine i alte
simboluri);
2. Presupunem c este un ir de simboluri din ( * ) i
considerm maina T n configuraia iniial 0 , $Q . Dac este
n L, maina T se va opri n configuraia , $H Y ;
*
0 , $ , $Q H Y pentru L ;
Dac nu este n L, atunci maina se va opri n configuraia
, $H N :
*
0 , $ , $Q H N pentru L .
Maina Turing trebuie s se opreasc pentru toate input-urile valide,
adic, ori de cte ori este pornit n configuraia 0 , $Q cu * .
Aceasta nseamn c T poate decide problema apartenenei pentru orice
ir * . Din acest motiv, limbajele recunoscute de o main Turing se
numesc i recunoscute n sens Turing. Deci, un limbaj poate fi descris i
de o main Turing bazat pe faptul dac maina se oprete, sau nu, cu un
ir dat. Spunem c un limbaj este acceptat de o main Turing LT T= dac
L se compune din acei pentru care T, eventual, odat pornit n
configuraia 0 , $Q , se va opri (coninutul benzii n momentul intrrii
n starea de oprire este vid). Dac un limbajul L este acceptat de o main
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 considerm
unele exemple.
-
Exemplu 5.1. Vom proiecta o main Turing care va recunoate
limbajul
{1 | 1,3,5, }nL n= = K
adic, limbajul irurilor formate dintr-un numr impar de 1-uri. Ideea de
baz a unei astfel de maini T este urmtoarea: Pornit n configuraia
0 , $11 1Q K va muta capul spre dreapta, alternnd ntre dou stri pentru
a contoriza numrul de 1-uri, pn cnd ntlnete #. Atunci se va deplasa
la stnga, nlocuind toate simbolurile de band cu #, pn ce ajunge
captul stng al benzii; apoi scrie Z pe band i se oprete. Descrierea
formal a mainii este urmtoarea:
1. Alfabetul este {$, 1, , , #}Y N .
2. Strile sunt: 0Q , starea iniial; 1Q , numr par de 1-uri ntlnite
pn aici; 2Q , numr impar de 1-uri ntlnite pn aici; 3Q , numrul
de 1-uri din este par, mut capul napoi pe $; 4Q , numrul de
1-uri din este impar, mut capul napoi pe $; 5Q , scrie Y i se
oprete; 6Q , scrie N i se oprete; H, starea de oprire.
3. Funcia de tranziie este dat de diagrama din figura 5.4.
-
Figura 5.4. Main Turing care recunoate un limbaj.
n figura 5.5. valorile funciei de tranziie sunt date sub form tabelar.
Funcia nu este definit pentru toate valorile de Q i x. Considerm
acum, ca exemplu, micrile mainii 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 oprete, 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 funcie de tranziie .
-
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 oprete, irul de intrare nu este n .
Q Q Q QQ Q Q QQ Q Q Q H N
L
Aceast main, fiind simpl i direct, nu este foarte interesant.
Limbajul din cauz a fost deja recunoscut de un automat finit. Dm acum
un exemplu de main Turing care va recunoate 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 main Turing care recunoate limbajul
{ | 0,1, 2, }n n nL a b c n= = K . Maina T se va comporta n felul urmtor: Fiind
dat un ir de a-uri, b-uri i c-uri ( *( ) + +a b c ), maina, odat pornit
n configuraia 0 , $Q , se va opri n configuraia , $H Y dac c
aparine limbajului sau n , $H N dac nu aparine limbajului. O
scurt privire asupra operaiilor ei este urmtoarea:
1. Va avea strile 1C , 2C , 3C . Dac T decide c aparine limbajului,
va intra n starea 1C urmnd s goleasc banda i se oprete n
configuraia , $H Y .
2. Va avea strile 1D , 2D , 3D . Dac T decide c nu aparine
limbajului, va intra n starea 1D i trece n configuraia , $H N .
3. Va utiliza strile 1 5E E pentru a determina dac este de formai j ka b c , adic, dac * * * a b c . Aceasta se face, ncepnd din
-
configuraia 1, $E , prin deplasarea capului spre dreapta i
intrarea n starea 2E . Dac este ntlnit a, capul continu s se
deplaseze la dreapta ateptnd apariia lui b, la care T intr n starea
3E . Capul se deplaseaz atunci din nou spre dreapta pn cnd este
ntlnit c iar starea se schimb n 4E . Capul continu deplasarea
spre dreapta pn ce ntlnete #, deci * * * a b c . Dac ceva merge
greit, maina intr n starea 1D .
4. Mai departe, se determin dac numrul de a-uri, b-uri i c-uri este
acelai. 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 numrul de a-uri i b-uri este acelai, capul este
poziionat la nceputul irului i oscileaz, nainte i napoi, ntre
a-uri i b-uri. De fiecare dat cnd ntlnete un a, acesta se
schimb n p, iar capul se deplaseaz la dreapta pentru a gsi un b.
Odat gsit, este schimbat n q, iar capul se deplaseaz napoi
pentru a gsi alt a. Dac nu mai gsete nici unul, maina verific
dac exist b-uri nemarcate, adic, dac toi b au fost schimbai n
q-uri. Din nou, dac merge ceva greit, maina intr n starea 1D .
Toate acestea au loc n timp ce maina rmne ntr-una din strile
1F , 2F , 3F , 4F . Mai rmne de artat c numrul de p-uri este egal
cu numrul de c-uri (fiecare a a fost schimbat n p, deci exist
attea p-uri ci au fost de a). Aceasta are loc n timp ce maina se
mic ntre strile 1G , 2G , 3G ; ideea este aceeai ca la compararea
de a-uri i b-uri.
Aceasta nu este cea mai eficient modalitate de construire a mainii
discutate; schema a fost aleas doar din motive de claritate. Formalitile
construcie sunt urmtoarele:
-
1. Maina are urmtoarele stri:
0Q , 1Q pentru pornirea operaiei; (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 numrul de a-uri i b-uri
este acelai
1G , 2G , 3G pentru a determina dac numrul de a-uri i c-uri este
acelai
2. Alfabetul benzii este {$, , , , , , , , , , #}a b c p q r s Y N = .
3. Starea iniial este 0Q .
4. Funcia de tranziie este dat dup cum urmeaz:
Strile 1C , 2C i 3C : Dac maina intr n starea 1C , a determinat c
irul este n limbaj iar tot ce rmne de fcut sunt operaii de
golire:
1 1( , ) ( , , )C x C x R = pentru toi #x (Localizeaz primul simbol din
dreapta)
1 2( , #) ( , #, )C C L =
2 2( , ) ( , , )C x C x L = pentru toi $x (terge toate simbolurile de pe
band exceptnd $)
2 3( , $) ( , $, )C C R =
3( , #) ( , , )C H Y L = Scrie Y pe band i se oprete.
-
Strile 1D , 2D i 3D : Micrile sunt la fel ca mai sus, cu excepia c
simbolul N trebuie scris la sfrit:
1 1( , ) ( , , )D x D x R = pentru toi #x 1 2( , #) ( , #, )D D L =
2 2( , ) ( , #, )D x D L = pentru toi $x 2 3( , $) ( , $, )D D R =
3( , #) ( , , )D H N L =
Strile 1 5E E . Pornim n configuraia 1, $E , ne deplasm la
dreapta, ateptnd s gsim 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 urmtoarea etap. Orice deviere de la ceea
ce ne ateptm 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 maina a determinat c * * * a b c , deci trebuie s
mute capul napoi la $ i s continue cu urmtorul set de teste:
4 5( , ) ( , , )E x E x L = pentru toi $x , 5 1( , $) ( , $, )E F S = . n toate
celelalte cazuri, 1( , ) ( , , )jE x D x R = . (Continu cu respingere.)
Strile 1 4F F : Obiectivul este aici de a determina dac numrul de
a-uri este acelai cu numrul de b-uri. ntruct am ajuns
-
configuraia 1, $F , suntem asigurai c este de forma i j ka b c .
ncepem cu mutarea capului spre dreapta pn la gsirea lui a.
Atunci starea va fi schimbat n 2F i a nlocuit cu p. Capul va
continua s se deplaseze la dreapta (presupunnd numai a-uri i
q-uri pe acest drum) pn ce ntlnete un b. La ntlnirea unui b,
acesta se schimb n q, capul se ntoarce la celula cea mai din
stnga ($) i procedeul ncepe de la nceput. irul trece de testul
de apartenen la L dac ncepnd de la $ i mergnd spre dreapta,
maina nu gsete 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 = (Gsete i
marcheaz un a.)
2 2( , ) ( , , )F x F x R = pentru ,x a q= ; 2 3( , ) ( , , )F b F q L = (Gsete i
marcheaz un b.)
3 3( , ) ( , , )F x F x L = pentru $x ; 3 1( , $) ( , $, )F F R = (ncepe din nou
cutarea unui a.)
1 4( , ) ( , , )F c F c L = ; (Toate a-urile i b-urile sunt potrivite, este
timpul pentru a vedea dac numrul de p-uri este egal cu numrul
de c-uri.)
4 4( , ) ( , , )F x F x L = pentru toi $x ; 4 1( , $) ( , $, )F G S =
n toate celelalte situaii 1( , ) ( , , )jF x D x R = (irul nu este din L).
Strile 1 3G G . Aici se determin dac numrul se a-uri (p-uri) este
egal cu numrul de c-uri. Ideea de baz este analoag
comportamentului din strile F; formularea exact este urmtoarea:
-
1 1( , ) ( , , )G x G x R = pentru $, , ,x r p s= ; 1 2( , ) ( , , )G p G r R = (Gsete
i marcheaz un p.)
2 2( , ) ( , , )G x G x R = pentru , ,x p q s= ; 2 3( , ) ( , , )G c G s L = (Gsete 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 = (Numrul de p-uri este egal cu numrul de c-uri
deci L .)
n toate celelalte situaii 1( , ) ( , , )jG x D x R = .
n final, ntreaga operaia ncepe n configuraia 0 , $Q . Aadar:
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.)
Ilustrm comportarea lui T cu input-ul aabbcc = . Micrile 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
55 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 MAINI TURING
n exemplele 5.1. i 5.2. am reconstruit maini Turing care serveau
rolului de a recunoate diferite tipuri de limbaje. Maina a decis dac un
ir de intrare dat a fost valid sau nu, adic, au decideau dac un ir dat
aparinea unor limbaje anume. Mainile Turing pot deservi i rolul de
calculator sau computer. Mai precis, dac presupunem c ( )f n este o
funcie 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 main Turing fT cu urmtoarea
-
proprietate: Pentru un input oarecare format din n de 1, maina fT va
trece din configuraia iniial
0de ori 1
, $111 1n
Q K123
n configuraia de oprire
de ( ) ori 1
, $ 111 1f n
H K123
Exemplu 5.3. Vom construi un exemplu de main Turing T
pentru funcia ( ) 2f n n= . Practic, maina va funciona n felul urmtor:
1. Pornind din cea mi din stnga celul a benzii, maina se deplaseaz
la dreapta pn ce gsete simbolul 1. Odat ntlnit, 1 este nlocuit
cu a iar capul continu s se deplaseze spre dreapta pn ce a
ntlnit i nlocuit primul simbol blank # cu b.
2. Capul se ntoarce la celula cea mai din stnga i ncepe cutarea
unui alt 1. Odat gsit, acest 1 este din nou nlocuit cu a iar primul
simbol blank cu b.
3. Pasul 2 se repet atta timp ct mai sunt 1-uri n input-ul. De vreme
ce nu mai exist 1-uri, banda va conine n de a i n de b. Toate
acestea sunt din nou nlocuite cu 1 iar maina se oprete.
Formal, aceast main este schiat de diagrama din figura 5.6.
Starea 1Q este folosit pentru gsirea i nlocuirea urmtorului 1 cu a, 2Q
gsete primul # disponibil i-l nlocuiete cu b, 3Q mut capul napoi pe
cea mai din stnga celul, 4Q nlocuiete a-urile i b-urile cu 1-uri i trece
-
n starea de oprire la apariia lui $. Alfabetul benzii este {1, , , $, #}a b = .
Simbolul $ este introdus aici, ca i n exemplul anterior, pentru
simplificare pentru a marca cea mai din stnga celul a benzii dar poate
fi omis, ceea ce ar face maina mai complicat. Considerm, de pild,
micrile acestei maini 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 14 4 4 4
4
, $ , $ #, $ , $ 1 , $ 11 , $ 111, $1111 , $1111 O alt demonstraie c 2*2 4.
b Q aabb Q aabbQ aabb Q aab Q aa Q aQ H
=
Figura 5.6. O main Turing care calculeaz.
Conceptul funciilor calculabile nu trebuie restrns doar la funciile
ntregi. O funcie calculabil pot fi vzut 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 rndul ei dintr-un ir
finit de simboluri (potenial diferite).
Definiia 5.3. Fie 1 i 2 dou alfabete (mulimi finite, nevide de
simboluri), care, pentru simplificare, presupunem c nu conin
simbolurile $ i #. Fie ( )f o funcie a crei argumente sunt iruri de
simboluri din 1 i ai crei 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 main
Turing fT astfel nct oricnd ( )f = , maina fT va trece din
configuraia iniial 0 , $Q n configuraia de oprire , $H . Cu alte
cuvinte fT va transforma input-ul n output-ul ( )f .
Definiia acoper toate situaiile posibile. De exemplu, o funcie de
valori ntregi cu trei variabile ( , , )w f x y z= este calculabil Turing dac
exist o main 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. Aadar, dac
( , , ) 3 4w f x y z x y z= = , astfel ca (1,2, 3) 2f = , maina Turing pentru f
-
are de transformat irul 1|11| 111 n 11 , adic, trece din configuraia
0 , $1|11| 111Q n , $ 11H .
Mainile Turing sunt acceptate ca noiuni 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 main Turing care, alimentat cu o band care conine
descrierea acestei probleme, va executa o secven finit de micri i se
va opri cu banda coninnd soluia problemei. Exist alte definiri de
algoritmi i funcii efectiv calculabile, dar ele sunt echivalente cu cea dat
anterior. Afirmaia c orice procedur efectiv calculabil, sau orice
algoritm, poate fi implementat de o main 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 funcie este calculabil i dac orice
problem are un algoritm care s-o rezolve. Mai exact prin aceasta se
nelege urmtorul lucru:
1. Este adevrat c pentru o funcie oarecare dat :f , exist o
main Turing fT care pentru orice n va executa urmtoarea secven de
micri:
{ {*
0de ori 1 de ( ) ori 1
, $11 1 , $ 11 1n f n
Q HK K
2. ntrebarea Are fiecare problem un algoritm care o va rezolva?
este desigur prea vag i neprecis pentru orice analiz matematic
raional. O vom formula astfel: Presupus c C este o clas de probleme,
fiecare din ea putnd fi complet descris de un numr finit de simboluri
dintr-un alfabet fixat . n plus se presupune c fiecare problem din C
-
este bine definit, adic, poate fi rspuns cu Da sau Nu. A ntreba de
existena unui algoritm pentru a rezolva toate problemele din C nseamn
a ntreba urmtoarele: Exist o main Turing CT care pornit n
configuraia 0 , $Q , unde este descrierea unei probleme din C, se va
opri n configuraia , $H Y dac rspunsul pentru este Da i se va
opri n configuraia , $H N dac rspunsul pentru este Nu. Exprimat
n aceti termeni, un algoritm este atunci doar o alt funcie efectiv
calculabil *: { , }f Y N
Surprinztor rspunsul la aceste dou ntrebri este nu. Exist
funcii necalculabile i probleme nerezolvabile. Afirmaia are, desigur, o
varietate de implicaii filosofice, care ns nu vor fi atinse aici. n schimb,
restul capitolului va fi consacrat expunerii explicite a acestor probleme i
funcii.
5.4. EXTENSII ALE MAINILOR TURING
O proprietate curioas, dar esenial, a mainilor Turing este c
puterea lor de calcul nu poate fi cu mult mbuntit. Putem considera,
de pild, maini Turing cu mai multe benzi, definirea exact fiind mai
mult sau mai puin evident. Se descoper c orice funcie care poate fi
calculat de o astfel de main poate fi calculat i de o main standard
(cu o band). Alt posibilitate este de a permite mainii Turing s aib
mai multe capuri de citire din nou nu se obine nimic prin aceasta. Tot
ce poate fi calculat de aceste maini presupuse mai puternice poate fi
calculate i de maini Turing standard.
-
Situaia este similar cnd considerm maini Turing
nedeterministe. Definiia lor concret este exact ca mai sus, cu excepia
c funcia de tranziie ( , )Q x poate avea valori multiple: Dac maina se
afl n starea Q iar capul ei puncteaz spre simbolul x de pe band atunci
( , )Q x d lista micrilor legale posibile. Este dificil s vorbim de un
limbaj recunoscut de o main Turing nedeterminist, ntruct, n funcie
de input-ul iniial, alegeri diferit de micri pot duce la rezultate diferite.
Putem, ns, vorbi de un limbaj L acceptat de o main Turing
nedeterminist. Fiind dat o astfel de main Turing T, limbajul TL
acceptat de L se compune din acele iruri pentru care exist secvene
de micri legale, ncepnd cu configuraia 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 acceptrii limbajelor, mainile nedeterministe
nu sunt mai puternice dect cele deterministe: Dac un limbaj L este
acceptat de o main Turing nedeterminist 1T , este acceptat i de o alt
main Turing determinist 2T . Astfel, situaia este asemntoare cu cazul
automatelor finite, dar diferit de automatele push-down.
Nu vom demonstra toate aceste rezultate raionamentele sunt
lungi i nu conduc la o ptrundere mai adnc 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 main Turing cu dou benzi este echivalent cu o
main standard cu o band. Mai precis, o main Turing cu dou benzi
va avea i dou capuri. Aadar funcia de tranziie a acestei maini 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 instruciunile
corespunztoare pentru mutarea capurilor la dreapta ( iN R= ), stnga
( iN L= ) sau deloc ( iN S= ). O configuraia a maini va fi descris de
1 1 1 2 2 2, , Q x x
unde Q este starea curent i i i ix este coninutul benzii i, 1, 2i = (locaia
capului este marcat prin subliniere).
Figura 5.7. O main Turing cu dou benzi.
De exemplu, maina Turing cu dou benzi din figura 5.7. se afl n
configuraia 7 , # , Q accb a abbacca . Dac, 7 3( , , ) ( , , , , )Q c a Q b L b R = ,
urmtoarea configuraie a mainii va fi 3, # , Q accb a bbbacca .
Fie L un limbaj peste un alfabet . Spunem c L este recunoscut de
o main Turing cu dou benzi 2T dac pentru oricare din * sunt
adevrate urmtoarele:
L implic *
0 , $ , $ , $ , $Q H Y
Starea curent 7Q
Banda 2
Banda 1
-
L implic *
0 , $ , $ , $ , $Q H Y
Cu aceste notaii avem:
Teorema 5.1. Fie L un limbaj peste un alfabet . Atunci L este
recunoscut de o main Turing cu dou benzi 2T dac i numai dac este
recunoscut de o main standard cu o singur band 1T (definiia 5.2.).
Demonstraie. Dac un limbaj este recunoscut de o main cu o
band 1T , este evident recunoscut i de o main cu dou benzi 2T : nu
micm al doilea cap. Formal, dat fiind 1 0{Q, , , }T Q = , maina 2T va
avea aceleai stri i acelai alfabet ca 1T , iar funcia ei de tranziie va fi
2 1 ( , , ) ( , , , , )Q x y Q x N y S =
unde 1 ( , ) ( , , )Q x Q x N = mutm primul cap din 2T n aceeai manier ca
capul din 1T , iar al doilea cap l lsm s puncteze ntotdeauna spre celula
cea mai din dreapta. Partea dificil (i interesant) a demonstraiei este de
a arta c dac un limbaj L recunoscut de o main cu dou benzi, este
recunoscut i de o main standard cu o singur band. La prima vedere
se pare c avnd la dispoziie o a doua band obinem o mai mare putere
de calcul: Putem memora informaie pe o band n timp ce lucrm cu
cealalt. Vom vedea c acesta nu este cazul. O demonstraie formal
complet este grea, cu multe implicaii i oarecum dincolo de scopul
acestei lucrri. Vom prezenta o schi a ideii principale.
Fie 2T o main Turing cu dou benzi care recunoate un limbaj L.
Notm capurile cu 1h i 2h . Vom construi mai nti o main auxiliar cu
-
o band U care va simula micrile lui 2T dup cum urmeaz. Fiecare
celul a benzii mainii U va conine: simbolul , simbolul blank %
(pentru a-l putea deosebi de simbolul blank # al mainii 2T ), sau un
cvadruplu 1 1 2 2( , , , )a a . Simbolul se va afla ntotdeauna n celula cea
mai din stnga i nu va fi eliminat niciodat. Cvadruplul 1 1 2 2( , , , )a a
din celula a i-a din U va conine informaia despre celulele i de pe benzile
mainii 2T . (Indexarea celulelor din U ncepe de la 0: celula cea mai din
dreapta a lui U este celula 0, urmtoarea este prima celul etc. Celulele
din 2T vor fi indexate ncepnd cu 1: celula cea mai din stnga a fiecrei
benzi din 2T este referit ca celula numrul 1, urmat de celula numrul 2,
etc.)
Figura 5.8. O celul a mainii Turing U.
Dac celulele i de pe benzile mainii 2T conine simbolurile x respectiv y,
atunci celula a i-a din U conine 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 = ; aceeai regul se aplic
simbolului 2 este egal cu 1 sau 0 n funcie 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 mainii
2T se afl n configuraia din figura 5.9., banda maini U va fi de forma
dat n figura 5.10.
-
Figura 5.9. Benzile unei maini Turing cu dou benzi.
Comportamentul mainii U este acum evident: O singur micare a
mainii 2T va rezulta n schimbarea strii mainii, coninutul a dou celule
(cte una de pe fiecare band) i reajustarea poziiilor capurilor de citire
1h i 2h . Fiecare astfel de micare a lui 2T va determin o secven de
micri a lui U, rezultnd ntr-o ajustare a celulelor sale valorile
relevante pentru ia -uri i i se schimb pentru a reflecta noua
configuraie a mainii 2T .
Figura 5.10. O band a unei maini Turing.
Formal, alfabetul U a mainii U este dat de o mulime finit
{, %} ( {0, 1} {0, 1})U =
Maina U i va ncepe activitatea cu capul punctnd pe celula cea mai
din stnga (coninnd simbolul ). Dup fiecare micare a lui 2T capul lui
se va deplasa la dreapta, fcnd ajustrile necesare, iar atunci se ntoarce
Banda 1
Banda 2
Toi #
Toi #
Toi %
-
la cea mai din stnga celul ateptnd urmtoarea micare a lui 2T .
Aceasta se poate realiza avnd strile 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 . Instruciunile mainii U pot fi acum
explicitate:
1. Pornete n starea 0 0 0 0 0 0( , , , ( , , ))Q x y Q x y cu capul punctnd spre
celula cea mi din stnga (coninnd simbolul ). Simbolurile 0x i
0y precum i coninutul iniial al benzii din U vor reflecta
configuraia iniial a mainii 2T .
2. Deplaseaz capul spre dreapta pn ce sunt ntlnite ambele cazuri
de 1i = . De fiecare dat, schimb valorile a-urilor i -urilor
relevante. (Informaia privind ceea ce este de fcut dac se
ntlnete 1 = este coninut n valoarea funciei 0 0 0( , , )Q x y .)
Noteaz aceste valori, fie ele Q , x i y ; se ntoarce la celula cea
mai din stnga (care poate fi depistat prin prezena lui ); i trece
ntr-o stare nou ( , , , ( , , ))Q x y Q x y .
3. Repet pasul 2 pn ce noua stare Q este starea de oprire H din 2T .
4. Golete prin a termina cu capul amplasat pe cea mai din stnga
celul i se oprete.
Ca urmare, este evident c maina cu o singur band U va simula
micrile mainii Turing cu dou benzi 2T orice decizie luat de 2T va fi
luat i de U. De asemenea este limpede c, prin adugarea unor stri
-
suplimentare la U, coninutul final al benzii poate fi transformat n forma
cerut de enunul teoremei 5.1. Q.E.D.
Trebuie remarcat faptul c adugarea unei benzi suplimentare la o
main Turing nu are efect asupra puterii de calcul a acesteia, dar are
definitiv efect asupra eficienei. Presupunem c 2T este o main Turing
cu dou benzi simulat de o main Turing cu o singur band 1T , ca n
teorema 5.1. Dac unul dintre capurile lui 2T este m celle ndeprtat de la
nceputul benzii i 2T face o micare, atunci 1T are de efectuat cel puin m
micri pentru a simula aceast singur micare. Dac 2T pornete cu
ambele capuri pe cele mai din stnga celule i la fiecare micare
amndou capuri se deplaseaz la dreapta, atunci i ia lui 1T cel puin21
21 2 k k+ + + L micri pentru a simula primele k micri ale lui 2T .
Aadar, vag vorbind, dac o main Turing necesit n micri pentru
rezolvarea unei anumite probleme, ne am putea atepta ca adugarea unei
benzi suplimentare va duce la rezolvarea problemei n n pai. Aceast
idee poate fi cu mult precizat; studiul complexitii de calcul se ocup cu
ntrebri de acest gen. Un cititor interesat poate consulta [13].
5.5. CODIFICRI
Evident c conceptul de main Turing este independent de modul
n care aceste maini sunt descrise. Aadar, nu conteaz dac notm
strile unui maini cu 0Q , 1,Q K, sau 1P , 2 ,P K . Ceea ce conteaz sunt
procesele interne ale dispozitivului adic, numrul de stri, numrul
de simboluri de band, relaia de tranziie i desemnarea diferitelor stri
drept stri interne i/sau de oprire. Vom prezenta acum o schem care
descrie uniform oricare i toate mainile Turing. Mai exact, fiind dat o
-
main Turing T, vom arta cum se d o descriere complet i neambigu
a lui T utiliznd doar un numr finit de simboluri fixate. De fapt, orice
main Turing poate fi descris folosind numai simbolurile B, A, E, P, X,
Y, L, R, S, 0 i 1. Se procedeaz astfel: Prin definiie, orice main Turing
se compune dintr-un numr finit de stri, un alfabet de band finit i un
numr finit de relaii de tranziie care implic doar strile i simbolurile
de band. Astfel, orice main 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 numrul de stri din T scris n notaie binar (adic,
utiliznd doar 0 i 1). Starea iniial are asociat numrul 1 i starea
de oprire numrul 1 .
2. 2. 2 Este numrul de simboluri de band din T, din nou scris n
notaie binar. Simbolul blank, care este un simbol de band pentru
oricare main Turing, va avea asociat numrul 1.
3. 3. 1 2, , , kT T TK sunt relaii de tranziie din T codificate n felul
urmtor. Fiecare stare i fiecare simbol de band din T are asociat
un numr unic strile au numere ntre 1 i 1 iar simbolurile de
band numere ntre 1 i 2 . Fiecare relaie de tranziie
( , ) ( , , )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 main Turing, notm 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 iniial (finit) de band a unei maini Turing
T poate fi codificar utiliznd 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 numrul de simboluri de band din T i 1 2, , , k K sunt
numerele acestor simboluri care apar efectiv pe band: 1 este numrul
simbolului de band din prima (cea mai din stnga) celul, 2 este
numrul simbolului din a doua celul, etc. Aceste numere
2 1 2, , , , k K sunt exprimate n notaie binar iar W, A, Z i F servesc
drept delimitatori. Se subnelege c simbolul din dreapta celulei k este
simbolul blank, a crui numr este 1. Codificarea prii iniiale 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. Considerm maina Turing dat de diagrama din
figura 5.11.
Figura 5.11. O main Turing T.
Aceast main are trei stri, deci 1 11 = (binar, 3 n decimal). Prin
convenie, starea iniial are asociat numrul 1 iar starea de oprire H
numrul 1 11 = ; aadar, 1Q are asociat numrul 10. Mai are 4 simboluri de
band: a, b, c i #, deci 2 100 = (n binar); prin convenie # are asociat
numrul 1 iar noi asociem 10 lui a, 11 lui b i 100 lui c. Tranziiile 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 maini 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 stng a benzii lui T ar fi #ab ac = , coninutul
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 maini mai complexe vor avea
codificri considerabil mai lungi, dar n principiu, orice main Turing i
orice parte finit a benzii poate fi codificat cu aceast schem.
Posibilitatea codificrii complete i neambigue a unei maini
Turing arbitrare i a input-ului ei ne permite s construim aa numita
main Turing universal 0U . n esen, o astfel de main simuleaz
orice alt main Turing n felul urmtor: Fie T o main Turing oarecare
i fie coninutul iniial al benzii lui T. Fie 1( )D T i 2 ( )D codificrile
pentru T i descrise mai sus. Punem maina T n configuraia iniial
0 , Q i maina 0U n configuraia 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 coninutul iniial al benzii din T n
maina 0U . Universalitatea lui 0U se bazeaz pe urmtoarea descriere a
comportamentului ei:
1. Dac, pornind din configuraia iniial 0 , Q , T se oprete
avnd ca coninut al benzii irul , atunci 0U , pornind din configuraia
0 1 2, ( )$ ( )Q D T D , se va opri de asemenea, cu banda coninnd irul
2 ( )D . Formal,
*
0 , , Q H implic *
0 1 2 2, ( )$ ( ) , D ( )Q D T D H
Poziia exact a capurilor celor dou maini este neesenial.
2. Dac T nu se oprete cu input-ul indicat, nu se va opri nici 0U .
Construcia formal exact a mainii 0U este greoaie, lung i
oarecum dincolo de scopul acestei lucrri. Vom prezenta doar ideea
principal; pentru detalii suplimentare cititorul este invitat s consulte
[13]. Maina Turing universal 0U va avea trei benzi T1, T2 i T3 cu
capurile corespunztoare 1h , 2h i 3h . Banda T1 va conine descrierea
codificat a mainii Turing T simulate i banda T2 va conine input-ul
iniial al lui T. Banda T3 va conine starea curent i locaia curent a
capului mainii T. Instruciunile mainii 0U sunt urmtoarele:
1. Introduce codificarea 1( )D T a mainii T pe banda T1, codificarea
2 ( )D a inputului iniial pentru T pe banda T2 i starea iniial a
-
lui T mpreun cu poziia capului lui T pe banda T3. Poziioneaz
toate capurile 1h , 2h i 3h la captul stng al benzilor
corespunztoare.
2. Deplaseaz capul 3h spre dreapta pn ce s-a gsite descrierea strii
curente i locaia curent a capului din T.
3. Utiliznd informaiile obinute la pasul 2, deplaseaz capul 1h pn
ce s-a gsit descrierea corespunztoarea a funcie de tranziie .
4. Utiliznd informaiile din paii 1 i 2, ajusteaz coninutul 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 golete dac
nu deplaseaz toate capurile de citire pe cea mai din stnga celul
i continu cu pasul 2.
Faptul c 0U are trei stri nu ridic probleme; conform teoremei
5.1, ea poate fi acum nlocuit de o main Turing standard cu o singur
band. Aceast idee se formalizeaz n felul urmtor.
Definiia 5.4. O main Turing 00 0{Q, , , }U Q = se numete
universal dac are urmtoarea proprietate. Fie 0 0{Q, , , }T Q = o main
Turing oarecare i fie un ir din * . Fie 1( )D T codificare lui T i 2 ( )D
codificarea lui . Maina T va executa secvena de micri*
0 , , Q H dac i numai dac maina 0U execut secvena de
micri
*
0 1 2 2, ( )$ ( ) , D ( )Q D T D H
-
Se presupune c mainile de mai sus ncep i nceteaz activitatea cu
capul amplasat pe cea mai din stnga celul.
Teorema 5.2. Exist o main Turing universal.
Remarcm faptul c exist o main Turing universal cu numai
dou stri. Construcia ei a fost dat de C. E. Shannon n [18].
Posibilitate codificrii oricrei maini Turing are o alt consecin
important: Este posibil listarea mainilor ntr-o singur secven
1 2 3 4, , , , T T T T K (0.5)
Orice main Turing posibil se va afla pe undeva n aceast list.
Enumerare de maini Turing se realizeaz astfel: Am vzut c o main
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 numr finit de iruri de
lungime n de fapt sunt exact 11n . Aadar, putem lista toate mainile
Turing ntr-o secven astfel: Mai nti listm toate mainile Turing a
cror descriere necesit doar un singur simbol (dac exist), atunci toate
mainile descrise de 2 simboluri (dac exist), etc. Cea mai mic
main Turing este
-
care are doar un singur simbol de band #. (Acesta este minimul ce poate
avea o main Turing.) Descrierea este 10 1B A PE , necesitnd un ir de
lungime 7 i st la nceputul secvenei (5.5). Aadar avem urmtoarele:
Teorema 5.3. Numrul de maini Turing distincte este numerabil.
n exact acelai mod, toate input-urile posibile a tuturor mainilor
Turing pot fi ordonate ntr-o singur secven. Aceasta rezult din faptul
c orice poriune finit a unei benzii poate fi descris utiliznd doar un ir
finit de simboluri A, W, Z, F, 0 i 1. Restul raionamentului rmne la fel.
5.6. PROBLEME DE DECIDABILITATE
n acest paragraf vom da o formulare precis (i soluia) problemei
discutate pe scurt n paragraful 5.3.
1. Are fiecare problem un algoritm care o rezolv?
2. Este fiecare funcie calculabil?
Aceste dou ntrebri sunt de fapt identice, ntruct soluia problemei
poate fi vzut ca funcie a descrierii problemei. A demonstra numai c
exist funcii necalculabile este uor. Din teorema 5.3. avem c exist
doar numerabil de multe maini Turing. Exist nenumerabile funcii
: {0,1}f , vezi Appendix 1. Aadar unele dintre aceste funcii (de fapt,
majoritatea lor) nu vor fi calculabile Turing. Acest argument, dei perfect
corect, este oarecum nesatisfctor, ntruct nu d un exemplu specific de
problem nerezolvabil sau funcie necalculabil. Vom da n acest
paragraf dou exemple concrete de acest tip.
-
Ne ntoarcem la ntrebarea existenei 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
main Turing care va rezolva aceea problem (teza lui Church-Turing).
Vom arta c nu exist un algoritm care, dac este dat descrierea unei
maini Turing T i descrierea inputului pentru T, va determina dac T
se oprete sau nu. Aadar, spunem c problema execuiei mainii Turing
este nedecidabil. n termenii mainii Turing aceasta poate fi formulat n
felul urmtor:
Teorema 5.4. Problema execuiei pentru maini Turing este
nedecidabil. Mai precis, nu exist o main Turing 0 0{Q, , , }A Q = cu
urmtoarele proprieti: Fie 0 0 {Q, , , }T Q = o main Turing oarecare i
fie un ir oarecare din * , i 1( )D T , 2 ( )D codificarea lui T respectiv
, descris n paragraful 5.4. Considerm comportamentul lui T la
input-ul (adic, comportamentul lui T pornit n configuraia 0 , Q , cu
capul punctnd spre cea mai din stnga celul). Mai considerm
comportamentul lui A la input-ul 1 2$ ( ) ( )D T D , adic, comportamentul lui
A pornit n configuraia iniial 0 1 2, $ ( ) ( )Q D T D . Dac T se oprete,
eventual, atunci A se va opri n configuraia , 1H , dac T nu se oprete
atunci A se va opri n configuraia , 0H .
Remarcm c T nu trebuie s se opreasc poate intra ntr-un ciclu
infinit sau se poate bloca; maina A trebuie s se opreasc ntotdeauna, cu
condiia 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 mainilor Turing i fie 1 2 3, , , K secvena tuturor input-urilor
-
admise pe aceast main. T-urile i -urile sunt codificate ca n
paragraful 5.5. Fie 0L mulimea acelor i pentru care maina iT nu se
oprete n configuraia , 1H . Aadar, o secven de input i este n
limbajul 0L dac i numai dac maina iT , pornit n configuraia( )0 ,
iiQ , nu se oprete deloc sau se oprete ntr-o alt configuraie dect
, 1H .
Lema 5.1. Nu exist nici o main Turing 0T care va decide pentru
fiecare i dac i aparine, sau nu, limbajului 0L . Mai precis, nu exist
nici o main 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
Demonstraie. Presupunem c o asemenea main 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 ntmpl dac pornim 00 i
T T= cu input-ul 0i
. Din ipotez,
00( )iT T= ea se va opri sau n configuraia , 1H sau n , 0H . n primul
caz, 0i
este n limbajul 0L , ceea ce nseamn c 0iT nu se oprete n
configuraia , 1H ; evident, este imposibil. Dac 00 i
T T= se oprete n
configuraia , 0 , 1H H , nseamn c 0i
este n limbajul 0L , aadar
0T i deci 0iT ar trebui s se opreasc n configuraia , 1H , dar am
presupus c aceasta nu are loc. Ca urmare, 0T nu poate decide cu
exactitate dac 0i
aparine limbajului 0L . Q.E.D.
-
Putem demonstra acum teorema 5.4. Ideea demonstraiei este de a
arta c dac o main Turing A, descris n teorema 5.4., exist, atunci se
poate construi o main 0T care recunoate limbajul 0L ca n lema 5.1.
Ceea ce este ns imposibil. Presupunnd c A exist, construcia lui 0T
este urmtoarea: Fiind dat un ir i , maina 0T trimite codificarea 2 ( )iD
i 1( )iD T la maina A. Dac A se oprete cu 0 pe banda (n configuraia
, 0H ), atunci 0T scrie 1 pe band i se oprete n configuraia , 1H .
(S-ar putea s aib de fcut unele operaii de golire.) Dac A se oprete cu
1 pe band (n configuraia , 1H ), atunci 0T trimite descrierile 1( )iD T i
2 ( )iD la maina universal 0U din teorema 5.2. Prin definiie, maina 0U
se va comporta la acest input n acelai mod ca maina iT cu input-ul i ,
adic se va opri. (ntruct A a anticipat, probabil corect, c iT se va opri.)
Dac U se oprete cu 1 pe banda sa, 0T va scrie 0 pe band i se oprete n
configuraia , 0H . Dac U se oprete cu banda coninnd alt ceva dect
1, atunci 0T va scrie 1 pe banda sa i se oprete n configuraia , 1H .
Este acum simplu de artat c maina 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 configuraia
, 1H . Exist dou posibiliti: i) iT nu se va opri deloc, sau ii) iT se va
opri, dar ntr-o alt configuraie dect , 1H . n cazul i), maina A se va
opri n configuraia , 0H deci, prin construcie, 0T se va opri n
configuraia , 1H , anticipnd corect c 0i L . n cazul ii), A se va opri
n configuraia , 1H , iar irul i , mpreun cu descrierea lui iT vor fi
introduse n maina universal 0U , care, la rndul ei, se oprete ntr-o
configuraie diferite de , 1H . Din nou, prin construcie, 0T se va opri n
-
configuraia , 1H , anticipnd corect c 0i L . De asemenea se vede
uor c 0T se va comporta corect dac 0i L , lsm demonstraia ca
exerciiu. Q.E.D.
Ne ndreptm acum atenia spre funcii necalculabile. Reamintim
c o funcie ( )f n m= (n, m numere pozitive) se numete calculabil dac
exist o main Turing fT care, la input-ul $111 1K (de n ori 1) va produce
ca output $111 1K (de ( )f n ori 1). O funcie f care nu este calculabil se
numete necalculabil.
Teorema 5.5. Exist o funcie necalculabil.
Demonstraie. Am vzut n paragraful 5.5. c exist o mulime
finit 1 astfel nct orice main Turing poate fi descris de un ir finit
de elemente (caractere) din 1 . De fapt, aceast mulime poate fi format
din 11 caractere distincte. n mod similar, orice input pentru o main
Turing poate fi descris de un ir finit de simboluri dintr-o mulime 2 ,
unde 2 este din nou finit. (n paragraful 5.5. mulime 2 are ase
elemente.) Fie T o main Turing i fie un input pentru T (adic,
coninutul iniial 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 numr finit de perechi
( , )T , unde T este o main Turing iar este input-ul ei iniial, astfel ca
( ) ( )p T q n+ . Fie nA mulimea acestor perechi. Dac ( , )T este o
pereche din nA , atunci T, cu input-ul , se poate opri sau nu. Fie nB
mulimea acelor perechi din nA care au proprietatea ca T s se opreasc la
input-ul . Din nou, nB se compune dintr-un numr finit de perechi.
-
Dac ( , )T este o pereche din nB , fie ( , )T desemnnd numrul de
micri pe care T le face naintea de a se opri n configuraia de oprire.
Definim acum o funcia ( )b n
( ) { ( , ) | ( , ) }nb n Max T T = B
n general, ( )b n este cel mai mare numr de micri pe care o main
Turing l poate executa asupra unui input , dac descrierea lui T i
luate mpreun nu depesc n simboluri. Funcia ( )b n astfel definit se
numete funcie busy beaver i nu este necalculabil. Presupunem c
exist o main Turing B care calculeaz ( )b n . Vom arta c aceast
implic c se poate construi o main Turing A care rezolv problema.
Aceasta, ns este imposibil, dup cum arat teorema 5.4. Pentru a
construi A procedm astfel: Fiind dat o main Turing i T cu inputul ,
maina A codific T i ca 1( )D T i 2 ( )D i calculeaz ( ) ( )n p T q = + .
Dup aceasta, A paseaz acest numr n mainii B i obine ( )b n . Avnd
acestea fcute, paseaz descrierile 1( )D T i 2 ( )D , ale lui T i , la
maina universal 0U i ncepe s numere micrile lui 0U . Dac 0U se
oprete nainte de ( )b n micri, A scrie 1 pe banda ei i se oprete n
configuraia , 1H . Dac 0U nu se oprete la a ( )b n -a micarea, A scrie 0
pe band i se oprete n configuraia , 0H . Este limpede c A se va
comporta corect: Dac 0U nu se oprete la a ( )b n -a micarea, nu o va face
nici T, ntruct 0U simuleaz pe T micare cu micare i ( ) ( )p T q n+ .
Q.E.D.
-
Merit fcute unele comentarii asupra ultimelor dou teoreme.
Dac teorema 5.4. afirm c problema de oprire a mainilor Turing este
nedecidabil, nu nseamn c nu putem decide, n unele cazuri specifice,
dac o main Turing dat se va opri, sau nu, la un input fixat.
Considerm, de pild, maina Turing descris n figura 5.12. Se observ
c dac maina T este pornit n configuraia 0 , Q ab nu se va opri
niciodat; dac ns este pornit n configuraia 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 main Turing care n unele cazuri se oprete iar n altele
nu.
Multe dintre ntrebrile legate de limbaje formale sunt
nedecidabile. Vom enumera aici cteva 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 main 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 existenei
unei astfel de maini Turing are sens.
Teorema 5.7. Este nedecidabil dac dou gramatici independente
de context au o propoziie comun.
Aadar, nu exist o main Turing care, pentru dou gramatici
independente de context 1G i 2G date, va decide dac 1 2( ) ( )L G L G = .
Vom arta n capitolul 6, c exist o procedur, adic, o main 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 surprinztor avem:
Teorema 5.9. Este nedecidabil dac o gramatic independent de
context arbitrar are o gramatic regular.
-
PROBLEME
1. Construii o main Turing care recunoate limbajul2{1 | 0,1, 2, }nL n= = K Artai micrile mainii cu input-urle 111 i
1111.
2. Construii o main Turing care va calcula funcia ( ) 3f n n= .
Artai micrile mainii cu input-ul 11.
3. Fie urmtoarea main 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. Artai micrile acestei maini ncepnd din configuraiile
0 , #Q abbaacaa , 0 , #Q bbaaca i 0 , #Q abbcaab .
b. Dai o diagram de stare a mainii.
c. Descriei neformal ce face maina.
4. Fie urmtoarea main Turing
-
a. Artai micrile mainii la input-ul ababbba = ncepnd cu
configuraia 0 , Q ababbba .
b. Dai o descriere tabelar a mainii.
c. Descriei neformal ce face maina.
5. Considerai o main Turing care compar dou numere m i n.
Maina ar trebui s treac din configuraia
{{0 , #11 1#11 1n m
Q K K n , #H x ,
unde , sau x f s e= n funcie dac n m> , n m< sau n m= .
6. Construii o main Turing cu o band infinit bidirecional car se
va opri dac i numai dac input-ul iniial conine simbolul a.
Acest simbol poate aprea oriunde pe band, nu neaprat n dreapta
poziiei iniiale a capului.
7. Construii o main Turing care recunoate limbajul*{ | { , } }RL a b = . Aici, R desemneaz inversul irului .
8. Dai codificri ale mainilor Turing din problemele 1 i 2, conform
descrierii din paragraful 5.5. De asemenea dai codificarea
-
coninutului iniial al benzii din configuraia iniial menionat n
aceste probleme.
9. Demonstrai c nu exist un algoritm care decide dac o main
Turing cu input iniial dat se va ntoarce cndva n starea iniial
0Q .
10. Demonstrai c nu exist un algoritm care decide dac o main
Turing cu input iniial dat va scrie cndva simbolul a pe band.