Calculabilitate

7/24/2019 Calculabilitate

1/14

Relaii, funciii calcul n sens Turing

Capitolele de mai jos introduc noiuni de baz privind construcia funciilorrecursive i unele noiuni de calculul n sens Turing, ca variant a calculabilitiiefective.

1 Relaii

O relaie Rpeste mulimileMi, i=1,n, este o submulime a produsului cartezianM1M2...Mn. Un element al relaiei R este un tuplu (x1,x2,...,xn) cu xiMi,i=1,n. Dac n=2 iM1=M2 spunem c R este o relaie binar pesteM i pentru(x,y)Rputem scrie x R y(de exemplu, scriem 25 ca alternativpentru (2,5)).

Domeniul dom(R), respectiv codomeniul ran(R), unei relaii binare RpesteM1iM2corespund mulimilor:

dom(R) =def{xM1,yM2| (x,y)R x}

ran(R) =def{xM1,yM2| (x,y)R y}

O relaie binarRpesteM1iM2este totaldac:

xM1,yM2(x,y)R (y,x)R

Relaia este total peste , n timp ce relaia


2/14

2 Cristian Giumale/Note de curs

Fie Ro relaie binarpeste o mulimeM. Spunem crelaia R este de:

preordine, daceste reflexivi tranzitiv; ordine parial, daceste de preordine i este antisimetric; ordine total, daceste de ordine pariali este total. echivalen, daceste simetric, reflexivi tranzitiv.

DacReste o relaie de echivalenpeste o mulimeM, iar xeste un elementdinM, definim clasa de exhivalena lui xca o mulime:

R[a] = {yM | (x,y)R}

De exemplu, este o relaie de ordine totalpeste, iar relaia

R={x,y| x+y este par(x,y)}

este o relaie de echivalen peste . Pentru orice x impar avem clasa deechivalenR[x] = {y| yeste impar}, iar pentru orice x par avem R[x] ={y| yeste par}.

Fie Ro relaie binarpeste o mulimeM. nchiderea refelexiva relaiei Restecea mai mic1relaie reflexivR'pesteMastfel nct RR'. Constructivist,

R'= {xM (x,x)} R

Fie Ro relaie binarpeste o mulimeM. nchiderea tranzitiva relaiei R, notatR+, este cea mai micrelaie tranzitivR'pesteMastfel nct RR'. Constructivist,

R+= Ui

iR

unde, R0= RRi+1= Ri{xM,yM,zM | (x,y)Ri(y,z)Ri(x,z)}, i1

Fie Ro relaie binarpeste o mulimeM. nchiderea reflexiv-tranzitiva relaieiR, notatR*, este cea mai mic relaie reflexivi tranzitivR'pesteMastfel nctRR'. Constructivist,

R*= { xM (x,x)} R+.

2 Funcii

O funcie fdinAn B, notatf:AB, este o relaie binarfABcare satisfacerestricia:

xA,yB,zB (x,y)f (x,z)f y=z

1R' este cea mai mic n sensul cpentru orice relaie reflexivR"exist implicaiaRR"R'R".


3/14

Cristian Giumale/Note de curs 3

Pentru orice xAexistcel mult o pereche (x,y)f. Dac(x,y)fspunem cfuncia este definitn punctul xi scriem y=f(x) nelegnd cf are valoarea y npunctul x. Prin convenie, dacfnu este definitn xscriem f(x)=, iar dacfestedefinitn xscriem f(x)sau f(x)=y, presupunnd csimbolul nu este nAi nicin B.

Domeniul funciei f:AB, notat dom(f), este submulimea punctelor dinA ncare feste definit. Codomeniul lui f, notat ran(f), este mulimea valorilor funciei f.La fel ca i pentru relaii,

dom(f)=def {xA | (yB (x,y)f)}

ran(f)=def{yB | (xA (x,y)f)}

Funcia f:AB este total (pesteA) dac xA (yB (x,y)f), decidacdom(f)=A. Altfel, dacdom(f)A, spunem cfeste parial(pesteA).

Funcia f:AB este injectiv dac pentru puncte distincte dinA are valoridistincte, adic

xdom(f),ydom(f) f(x)=f(y) x=y

Funcia f:AB este surjectiv dac yB (xA y=f(x)), deci dacran(f)=B.

O funcie f:ABtotal, injectivi surjectiveste bijectiv (o bijecieAB). nacest caz, spunem cmulimileAi Bsunt echipotente.

Dou funcii f:AB i g:AB sunt egale dac i numai dac au acelaidomeniu i aceeai valoare pentru fiecare punct din domeniu. Scriem f=gpentru aspecifica egalitatea funciilor.

f=g xA (f(x)=g(x)=) (yB f(x)=y g(x)=y)

Prin urmare f(x)=g(x)aratfie c:

fi gsunt definite n xi au aceeai valoare, fie c f(x)=ig(x)=

2.1 Funcii primitiv-recursive

O funcie f:n este obinut prin transformare direct dintr-o funcieg:mdac

f(x1,x2,...,xn) = g(v1,v2,...,vm)

unde xi, i=1,n, sunt variabile cu valori n , iar vjeste fie o variabilxi, 1in, fie oconstant din . Prin convenie, scriem f=Tr[g] pentru a indica posibilitatea


4/14


construciei lui f printr-o transformare explicit a lui g, dar fr a preciza detaliiletransformrii.

O funcie f:n este obinutprin compunere pe baza funciilor h:m,gi:

n, i=1,m, dac pentru orice vector de valorixn = (x1,x2,...,xn)

navem:

f(xn) = h(g1(xn), g2(x

n),..., gm(xn)), dac i1..m gi(x

n)

f(xn) = , dac i1..m gi(xn)=

Prin convenie, scriem f=Cp[h,g1,g2,...,gm]pentru a indica construcia lui fprin compunere.

O funcie f:n+1 este obinut prin recursivitate primitiv, pe bazafunciilor h:n+2, g:n , dac:

f(0,xn) = g(xn)

| h(m,xn,f(m,xn)), dacf(m,xn) f(m+1,xn) = |

| altfel

Prin convenie, scriem f=Pr[g,h] pentru a indica construcia lui f prinrecursivitate primitivpe baza funciilor gi h.

O funcie este primitiv-recursivdacpoate fi obinut printr-un numr finit depa

i de aplicare a opera

iilor de transformare direct

, compunere

i recursivitate

primitiv pornind de la funciile de baz: zeron, n0 (zeron este funcia n-arx1,x2,...,xn.0; n particular, funcia nular zero0 este constanta 0) i succ(funcia succesor x.x+1). Alternativ, clasa funciilor primitiv-recursive este cea maimicclasde funcii care conine funciile de bazzeroni succi este nchissuboperaiile de transformare direct, compunere i recursivitate primitiv. Prin urmare, ofuncie primitiv-recursivpoate fi scrisf=E, unde Econine doar transformri Tr, CpiPr aplicate funciilor zeron i succ. Se poate demonstra [Tay 98] c orice funcieprimitiv-recursiveste total2.

n exemplele de mai jos, convenim sscriem x1,x2,...,xn.calculpentru adesemna o funcie n-arcu parametrii xi, i=1,n, i cu un rezultat obinut conformcalculului calcul(parametrizat n raport cu xi, i=1,n). De asemenea, aplicaia f(x)

va fi scrisuneori i sub forma (f x).

id:este funcia identitate

id(0) = 0

id(n+1) = succ(id n) = (n,r.(succ r) (n,id(n)))

id = Pr[0, n,r.(succ r)] = Pr[zero0,Tr[succ]]

2 Funciile de baz sunt totale, iar transformarea direct, compunerea funcional irecursivitatea primitivgenerazo funcie totalprin aplicare asupra unor funcii totale.


5/14


pred:

pred(n) calculeazpredecesorul lui n, cu limitare la 0.

pred(0) = 0

pred(n+1) = n = id(n) = n,r.(id n) (n,pred(n))

pred = Pr[0, n,r.(id n)] = Pr[zero0,Tr[id]]

zerop:zerop(n) este 1dacn=0i 0altfel

zerop(0) = 1 = succ(0)

zerop(n+1) = 0 = n,r.0zerop = Pr[succ(0), n,r.0] = Pr[Cp[succ,zero0],zero2],

unde compunerea Cp[succ,zero0]este o rescriere la limita aplicaiei succ(0)

plus:2 plus(n,m) calculeazsuman+m

plus(0,m) = m = id(m)

plus(n+1,m) = succ(plus(n,m)) = n,m,r.(succ r)(n,m,plus(n,m))

plus = Pr[id, n,m,r.(succ r)]= Pr[id,Tr[succ]]

dif:2 dif(n,m) calculeaz diferena n-m, cu limitare la 0(dif(n,m)=0 dacn


6/14


O funcie este parial-recursiv dac poate fi obinut printr-un numr finit depai de aplicare a operaiilor de transformare direct, compunere, recursivitateprimitivi minimizare pornind de la funciile de bazzeron, n0,i succ. Alternativ,clasa funciilor parial-recursive este cea mai micclascare conine funciile de bazzeron i succ i este nchis sub operaiile de transformare direct, compunere,recursivitate primitiv i minimizare. Mulimea funciilor parial recursive includemulimea funciilor primitiv-recursive i, totodatconine i funcii care nu sunt totale3.Funciile parial-recursive care sunt totale se mai numesc i funcii recursive, deiacest termen este folosit uneori pentru a desemna o func ie recursiv fra precizaclasa ei.

De exemplu, funcia div(n,m) de mai jos calculeaz ctul mpririi ntregidintre numerele naturale n im i este parial recursiv. Predicatulmic(n,m)

rentoarce 1dacn


7/14


3 Calcul n sens Turing

Maina Turing, n particular maina Turing determinist, reprezint modelultradiional al calculabilitii, diversele modele fiind raportate n cele din urmla Turing-calculabilitate. Calculabilitatea efectiv este, de asemenea, raportat la Turing-calculabilitate, iar multe domenii ale tiinei calculatoarelor folosesc aparatulmatematic i proprietile mainii Turing ca bazteoretic.

3.1 O descriere informala mainii Turing

Dei a premers explozia tehnologiei digitale, maina Turing este apropiatcastructuri mod de funcionare de un calculator digital modern. Diferena principaleste c o main Turing este construit n mod special pentru un anumit calcul4.Similar cu un calculator numeric, o mainTuring particularMeste formatdintr-ounitate de control i o memorie.

Memoria este o banddeplasabil n faa unui cap Hde citire/scriere. Bandamainii este divizat n celule, iar lungimea ei (numrul de celule) nu este limitat.Fiecare celulmemoreazun simbol dintr-o mulime finit, numitalfabetul benzii.Fiecare celul poate fi citi i rescris, rescrierea distrugnd coninutul curent alcelulei. n existun simbol special, notat B (i numit "blank"), folosit pentru a marcacelulele libere de pe band. Micarea benzii este n cuante, o cuant de micarecorespunznd deplasrii benzii cu o celul, spre stnga sau spre dreapta, n faa

capului H. Simbolul aflat n celula poziionat n faa capului Heste denumit simbolulcurent scanat.

Unitatea de control este un automat finit determinist care controleazoperaiaexecutatde capul H(citire/scriere) i micarea benzii. Operaiile (sau instruciunile)ce pot fi executate de mainsunt:

1:2 Dacsimbolul curent scanat este 1el este rescris cu simbolul2. n particular, 1i/sau2pot fi B.

:R Dac simbolul curent scanat este atunci banda se deplaseazspre dreapta cu o celuln faa capului H.

:L Dac simbolul curent scanat este atunci banda se deplaseazspre dreapta cu o celuln faa capului H.

Se observ c execia instruciunilor este condiionat de simbolul curentscanat. De asemenea, cel mult o singurinstruciune este executabilla un momentdat pentru orice stare a mainii (determinism).

4Sunt prezentate, pentru simplitate, doar astfel de maini. Generalizarea exist, mainaTuring universalfiind programabil.


8/14


Diagrama tranziiilor efectuate de unitatea de control a mainii corespunde unuigraf orientat n care nodurile reprezintstri, iar arcele tranziii ntre stri. Fiecare nodeste etichetat cu un simbol de stare, notat convenional qk, dintr-o mulime finitdeasemenea simboluri. Un arc este etichetat cu instruciunea executat de main nmomentul parcurgerii arcului. Procesul de schimbare a strii mainii prin execuia uneiinstruciuni constituie un pas al calculului efectuat de main.

Prin convenie, se presupune c mainaM este ntr-o stare special q0 lanceputul calculului (stare iniial). Maina se oprete atunci cnd nici o instruciunenu mai poate fi executatpornind din starea curent.

b bB a

cap citire/scriere

B a BB

unitate control

a:L

0 1

b:a

B:L B:R

a:R

2

band

Figura 1O maindeterministTuring

Coninutul benzii i starea mainii se schimb n cursul funcionrii. Folosimtermenul configuraia benzii pentru a desemna coninutul benzii (al memoriei mainii)i poziia capului H la un moment dat de timp. De asemenea, termenul configuraiamainii desemneazconfiguraia benzii i starea curent a unitii de control la unanumit moment n cursul funcionrii.

Pentru a descrie calculul efectuat de main, un pas de calcul este reprezentatfolosind notaia:

...Bsqi

s'B... :...Bsqj

's'B...

Notaia arat c plecnd de la configuraia curent a benzii ...Bss'B...,undes,s'*, iareste simbolul curent scanat, i de la starea curentqiatunciprin execuia instruciunii :-cu aciunea {L,R}- configuraa benzii devine...Bs's'B...-unde 'este noul simbol scanat i starea mainii devine qj.

Scrierea ...B desemneaz un ir de simboluri aflate pe band la stngacapului Hi care este format doar din simboluri B. Scrierea B... desemneazun irde simboluri aflate pe band la dreapta capului H i care este format doar din


9/14


simboluri B. n cele ce urmeazconsiderm implicite punctele ce preced sau succedsimbolul Bdin specificarea unui pas de calcul.

Ca exemplu, se considermaina Turnig din figura 1 (preluatdin [Tay 98]). nconfiguraia iniiala mainii celulele benzii coin simbolul B(sunt libere) cu excepiaunei zone compacte ce memoreaz simbolurile a ib. Capul H este poziionat peprimul simbol diferit de Bde pe band, iar starea iniiala mainii este q0.

Calculul efectuat de main const n nlocuirea tuturor simbolurilor a de peband cu simbolurib. De asemenea, maina trebuie s se opreasc cu capul Hpoziionat ca n starea iniial: pe primul simbol non B de pe band. Calculul estedescris de urmtorii pai:

Bq baabB

b:a

Bq aaabB

(a:R)3

Baaaq bB0 0 0 b:a Baaaq0aB a:R Baaaaq B0 B:L Baaaq aB (a:L)4q1BaaaaB1 B:R Bq2aaaaB

unde (i)ndesemneazaplicarea de nori a instruciunii i. Se observcpentru oricestare a mainii cel mult o singur instruciune este executabil ntr-un pas. Mainaeste determinist.

3.2 Maini Turing deterministe

O mainTuring deterministMeste un qvintupluM = unde:

Q este o mulime finit i nevid de stri. Exist o stare q0Q singular,reprezentnd starea initiala mainiiM.

i sunt mulimi finite nevide astfel nct . este alfabetul de intrare alluiM (simbolurile ce constituie configuraia iniial a benzii luiM). este alfabetulcomplet al benzii luiM (simbolurile ce pot fi folosite n orice configuraie a benzii ncursul calculului executat deM).

: Q({L,R})Q este o funcie parialpeste Qnumitfuncie detranziie a luiM. Funcia primete o stare qii un simbol al benzii i rentoarce o

singuraciune {L,R}i o singurstare qj. Funcia codificpaii de calcul cepot fi executai deM. DacMeste n starea qii simbolul curent scanat este atuncimaina executinstruciunea :i trece n starea qj.

O main Turing poate fi folosit pentru a calcula funcii teoretice numerice(number-theoretic functions). Spunem c o funcie f este Turing calculabil dacexisto mainTuring care pentru fiecare configuraie iniiala benzii, reprezentndargumentul x al funciei, fie se oprete cu o configuraie a benzii ce corespunderezultatului f(x), dacxdom(f), fie nu se oprete, dacxdom(f).


10/14


Prin convenie, n exemplele urmtoare reprezentm numrul natural n ca osecvende n+1simboluri diferite de B, de exemplu 1..n+1

..1sau, prescurtat, 1n+1.Reprezentarea dezambigueazntre 0, care ar corespunde unei celule libere, i B.

Ca un prim exemplu de funcie Turing-calculabil, sconsiderm adunarea adou numere naturale: plus(n,m)=n+m, n, m. Numim plus maina carecalculeazfuncia i a crei diagramde tranziii este ilustratn figura 2.

0 1 2 3

457

1:R

B:R

1:R

B:L 1:B

1:L

B:L

B:L 1:B

1:L

6B:1

8B:R

B:L

Figura 2.Adunarea a dounumere naturale

Configuraia iniiala benzii mainiiplusconine reprezentrile numerelor nim, separate printr-un simbol B. Celelalte celule ale benzii sunt B(libere). Iniial, capul H

este poziionat pe primul digit al lui n (pe primul simbol 1 din reprezentarea lui n).Configuraia finala benzii conine reprezentarea numrului cu valoarea n+m, capul Hfiind poziionat pe primul digit al rezultatului.

...B 1n+1B 1m+1B... plus ...B 1n+m+1B...

H H

Paii calcululuiplus(n,m)au un efect simplu: ultimul 1dinmeste preschimbatn B, iar simbolul Bde separaie dintre nimeste transformat n 1atunci cndm1.

Iniial Bq 1n+1B1m+1B0 (1:R)n+1 B1n+1 B1m+1Bq0

B:R

B1n+1Bqm+111 B(1:R)m+1 1n+1B1m+1q1BB

B:L B n+1Bmq 1B1 1 2 1:BB1n+1B1mq3BB

Cazm=0 B1n+1Bq BB3 B:LB1n+1q BBB4 B:LB1nq 1BBB7 B

(B:L)n+1 B1n+1BBBBq7 B:RBq81

n+11BBBB


11/14


Cazm>0 B1n+1B1mq BB.3 B:LB1n+1B1m-1q41BB

1:BB1n+1B1m-1q5BBB

Cazm=1 B1n+1Bq BBB5 B:LB1n+1q6BBBB

B:1B1n+1q71BBB

(1:L)n+2 n+m+1BBBq7B1

B:RBq81n+m+1BBB

Cazm>1 B1n+1B1m-1q5BBBB:LB1n+1B1m-2q61BBB

(1:L)m-1 B1n+1q B1m-1BBB6

B:1

B1n+1q71mBBB

(1:L)n+2 n+m+1BBBq7B1

B:RBq81n+m+1BBB

Calculele complicate pot fi descompuse n fragmente mai simple, iar mainilecare calculez fragmentele pot fi combinate pentru a constitui o main carerealizeaz ntregul calcul. Bunoar, cuplarea n secven a dou maini Turingcorespunde compunerii funcionale. De exemplu, funcia dublu(n)=2*n poate ficalculatde o maindublu = plus o copie, rezultatprin cuplarea n cascadamainilorplusi copie. Maina copieconstruiete o copie a numrului n, iarplusrealizeazadunareaplus(n,n).

56

1

4

3

0

2

7 8

*:R

1:*

*:R

1:L

1:L

1:L

*:1

B:R

B:L

1:L

B:1

1:R

1:RB:R

Figura 3.Copierea a unui numr natural

O posibil implementare a mainii copieeste ilustratn figura 3. Configuraiainiial a mainii este Bq01

n+1B. Maina se oprete cu configuraia Bq81n+1B1n+1B.

Starea finaleste ntotdeauna q8.


12/14


Dacdin q8a mainii copieare loc o tranziie n starea q0a mainiiplus, aacum se arat n figura 4, atunci maina dublu rezultat prin compunerea plus ocopie calculeaz 2*n. Tranziia este q8( copi e) 1:q0( pl us) 1 i este ntotdeaunaposibil. ntradevr, chiar dacn=0, copia lui nare cel puin un simbol 1, iar capul Halmainii copie se afl poziionat pe primul 1 al lui n n starea q8( copi e) . Stareainiial a mainii dublueste starea iniialq0a mainii copie, iar starea finala luidublueste starea finalq8a mainiiplus.

mainde adunare:plus

0 8 0 81:1

mainde copiere: copie2nn

Figura 4.O mainpentru calculul 2*n = plus(n,copie(n))

Ca exemplu adiional, s construim o main Turing, numit count, caretesteaz egalitatea dintre numrul de apariii ale dou simboluri a ib ntr-un irs{a,b}*. Dac notm nx(s) numrul de apariii ale simbolului x n irul s, atuncicalculul realizat de maina counteste na(s)=nb(s). Maina countare o configuraieiniial a benzii astfel nct capul H este poziionat pe primul simbol al irului, iarconinutul benzii este BsB, unde s este irul de scanat. Dac na(s)=nb(s)configuraia finala benzii este B1B, iar dacna(s)nb(s)configuraia finala benzii

este B0B, unde simbolurile 1i 0sunt diferite fade aib.O posibilimplementare amainii count este ilustrat n figura 5. Maina recunoate propoziiile limbajuluiL={s{a,b}*| na(s)=nb(s)}: se termin ntotdeauna cu 1 dacsLi cu 0 dacsL.

a:R

B:R0

1

5

6

4

2

3

*:Ra:*

b:*B:1

*:BB:L

*:R

*:R

*:L

b:R

b:L

a:L

b:*

a:*

B:L7

B:L

B:L

*:B

8

9

B:L

B:0

b:B

a:B

...B1B......B0B...

Figura 5.O maincare recunoate limbajul L={s{a,b}*| na(s)=nb(s)}


13/14


Problemele date ca exemplu sunt modelabile prin funcii recursive. Urmtoareateorem, aratcTuring computabilitatea acoperexact aceastclasde funcii.

Teorem(Turing). Clasa funciilor Turing-calculabile este exact clasa funciilorparial-recursive.

Demonstraia este complicati depete domeniul analizei algoritmilor AA. Ovarianta demonstraiei poate fi gsitn [Tay 98].

3.3 Mainile Turing ca modele utile n programare

n afara caracterizrii funciilor numeric-teoretice, mainile Turing ocupun locimportant n teoria automatelor i limbajelor formale cu consecine directe nproiectarea i implementarea limbajelor de programare. Astfel, limbajele pot ficaracterizate dupcum sunt acceptate sau recunoscute de diverse tipuri de MainiTuring. Bunoar, maina count din seciunea 3.2 este capabil s disting ntreirurile de simboluri ce reprezintpropoziii n limbajul L={s{a,b}*| na(s)=nb(s)}i irurile care nu sunt propoziii ale limbajului. Spunem c o asemenea mainrecunoate limbajul (sau ceste un "recognizer" al limbajului). Daco mainMseoprete cu un anumit rezultat doar pentru propoziii sLi nu se oprete pentru irurisL, atunci mainaMeste un acceptor al limbajului L.

Similar, poate fi caracterizat decidabilitatea unor proprieti cu importanparactic imediat ale diverselor clase de limbaje. Bunoar, n cazul unui limbajindependent de context L(G)5, generat conform unei gramatici G, problemeleurmtoare nu sunt decidabile:

- S se decid dac L(G) este ambiguu (exist cel puin o propoziiederivabilprin secvene diferite de derivare).

- Sse deciddacL(G)=T*, unde T*este mulimea tuturor irurilor formatecu simbolurile terminale ale gramaticii G.

- Considernd dou limbaje independente de context L(G1)i L(G2), ssedeciddacL(G1)L(G1)=.

Maina Turing este apropiatde paradigma programrii imperative, folositde

majoritatea limbajelor de programare comerciale. La baza unui asemenea limbaj esteconceptul de stare a programului definitca mulimea valorilor variabilelor i valoareapunctului de control al programului la un moment dat n cursul execuiei i corespundeconfiguraiei unei maini Turing.

Un program imperativ scris bunoar n C poate fi privit ca o codificarecomod a diagramei tranziiilor unei maini int Turing, diagram ce controleaz

5 Limbajul L(G) este privit ca mulime a irurilor de simboluri terminale (iruri numitepropoziii) ce sunt formate conform regulilor gramaticii G.


14/14


modificarea unei benzi direct adresabile ce joac rolul memoriei datelor. Exist oorigine convenionala benzii, iar celulele sunt numerotate pornind de la 0n raportcu originea. Variabilele folosite de program sunt grupuri de celule ale benzii directaccesibile prin instruciuni de forma Lii Ri, unde ieste adresa primei celule din irulcompact de celule asociat varibilei. Starea programului este modificat folosindinstruciuni de atribuire i de control al fluxului execuiei ce sunt macro-expandate ninstruciunile de baz ale mainii intTuring sau pot fi executate de maini Turinginterconectate ca pri ale mainii int.

De asemenea, cu unele extinderi, ecartul dintre o mainTuring i un calculatornumeric programabil poate fi diminuat. O asemenea extindere corespunde mainiiTuring universale: o maincapabilspreia ca intrare un program PT, reprezentndcodificarea unei maini Turing T, i o configuraie ia benzii lui T. Maina emuleaz

execuia mainii Tcu configuraia iniialia benzii, deci practic executT(i). MainaTuring universaleste conformconceptului de calculator cu program memorat.

Calculabilitate

Documents

Transcript of Calculabilitate