Tema:

”Mașina Turing si aplicațiile

algoritmice”Elaborat de

Studenții grupei CIB-112:

Burleai Daria

Dumbrava Marin

Verificat de profesorul:

Tutunaru Sergiu

Scurt istoric• Fondatorul Mașinii Turing-Alan Turing(1912-1954) •A descifrat codurile folosite de armata germană, fapt care, potrivit multor istorici, ar fi salvat vieţile a milioane de oameni, prin scurtarea duratei războiului, şi a fost foarte aproape de a rezolva o enigmă biologică care îi pasionează şi în zilele noastre pe oamenii de ştiinţă.

•În 1936, Alan Turing, care anunţase că vrea să "construiască un creier", a publicat un articol în care a descris "maşina universală Turing".

Apariţia maşinii care-i poartă numele este dată de încercarea de a rezolva una dintre problemele celebre propuse de David Hilbert, Entscheidungsproblem „este matematica decidabilă?” Există un algoritm care, pornind de la o descriere formală a unei probleme matematice, să poată determina valoarea de adevăr a problemei. În construcţia teoretică a acestei maşini, a pornit de la o idee inspirată de maşina de scris; astfel, maşina de scris poate fi considerată ca având o memorie de lungime infinită (prin schimbarea continuă a foilor), se poate mişca înainte şi înapoi la o căsuţă de memorie, poate scrie în aceste căsuţe.

Scurt istoric

Noi facilități introduse de Turing

Ștergerea unui simbol

din memorieSimbolul Blank

Citirea simbolurilor din căsuţe

Număr mare de configurații

Stări interne

Maşina Turing este compusă din următoarele piese:

o bandă infinită de hîrtie cu pătrăţele - în fiecare pătrăţel se poate scrie exact un caracter din alfabetul nostru;

un cap de citire-scriere - se poate mişca deasupra benzii, la stînga sau la

dreapta;   o unitate de control- conţine un număr finit de reguli care indică maşinii ce să

facă la fiecare mişcare în funcţie de litera curentă de pe bandă şi starea în care maşina se află.

Fig.1 Schema Mașinii Turing

FuncFuncțționareaionarea O maO mașșininăă Turing func Turing funcțționeazioneazăă cu un set finit de st cu un set finit de stări ări S={s1,….sn; sn+1=stop} unS={s1,….sn; sn+1=stop} un alfabet finit de simboluri alfabet finit de simboluri A={a1……aA; aA+1= blank}A={a1……aA; aA+1= blank} șși un set finit de instruci un set finit de instrucțțiuni , la care iuni , la care

se adaugse adaugăă o band o bandăă infinit infinit de de lung lungăă de memorie. de memorie. StStăările corespund la moduri de funcrile corespund la moduri de funcțționare a maionare a mașșinii, astfel inii, astfel îîncncîîtt

mamașșina Turing este ina Turing este îîn exact una dintre aceste stn exact una dintre aceste stăări la orice moment ri la orice moment de timp. de timp.

Simbolurile din A codeazSimbolurile din A codeazăă informa informațția prelucratia prelucratăă de ma de mașșininăă: codeaz: codeazăă datele de intrare/iedatele de intrare/ieșșire ire șși pi păăstreazstreazăă rezultatele opera rezultatele operațțiilor iilor intermediare.intermediare.

InstrucInstrucțțiunile sunt asociate cu iunile sunt asociate cu ssttăări din S ri din S șși spun mai spun mașșinii ce acinii ce acțțiune iune ssăă efectuez efectuezee dac dacăă îîntntîîlnelneșște un simbol dat, te un simbol dat, șși i îîn ce stare sn ce stare săă fie dup fie dupăă efectuarea acestei acefectuarea acestei acțțiuni.iuni.

ExistExistăă o stare “stop” o stare “stop” îîn urma cn urma căăreia nu se efectueazreia nu se efectueazăă nici o nici o instrucinstrucțțiune, aceastiune, aceastăă stare nefiind inclus stare nefiind inclusăă îîn numn număărul total de strul total de stăări.ri.

Capul de citire/scriere poate efectua trei Capul de citire/scriere poate efectua trei acacțțiuni: iuni:

1) sc1) scrrierea sau ierea sau șștergerea de pe bandtergerea de pe bandăă a a conconțținutului celulei care este scanatinutului celulei care este scanată.ă.

2) schimbarea st2) schimbarea stăării interne a marii interne a mașșinii inii

3) mi3) mișșcarea capului cu o celulcarea capului cu o celulăă la stanga la stanga sau dreapta.sau dreapta.

IIn ciuda faptului cn ciuda faptului căă este nepractic este nepracticăă, ma, mașșina Turing este un concept ina Turing este un concept matematic esenmatematic esențțial pentru dezvoltarea calculatoarelor. Din fericire, ial pentru dezvoltarea calculatoarelor. Din fericire, operaoperațțiile maiile mașșinii Turing pot fi inii Turing pot fi îînlocuite de pornlocuite de porțți logice. i logice.

O poartO poartăă logic logicăă este un circuit electronic care implementeaz este un circuit electronic care implementeazăă, , îîn n calculatoarele clasice, o operacalculatoarele clasice, o operațție logicie logicăă care transform care transformăă o stare n-bit de la o stare n-bit de la intrare intrare îîntr-o ientr-o ieșșire m-bit.ire m-bit.

OperaOperațția logicia logicăă este numit este numităă Boolean Booleanăă dac dacăă ac acțționeazioneazăă doar asupra doar asupra valorilor logice 0 valorilor logice 0 șși 1. i 1.

EchivalenEchivalențța a îîntre mantre mașșinile Turing inile Turing șși circuitele logice clasice este susi circuitele logice clasice este susțținutinutăă de urmatoarea propozide urmatoarea propozițție (ie (îîn sens matematic):n sens matematic):

O problemO problemăă din clasa polinomial din clasa polinomialăă P, se poate rezolva pentru date de P, se poate rezolva pentru date de lungime n de o malungime n de o mașșininăă Turing Turing îîn timp polinomial p(n) dacn timp polinomial p(n) dacăă șși numai daci numai dacăă îîi este asociati este asociatăă o familie de circuite cu un num o familie de circuite cu un număăr de porr de porțți de ordinul i de ordinul p(n)logp(n)logpp(n)(n)..

IpotezaIpoteza : : orice funcorice funcțție ce se presupune ie ce se presupune îîn n mod natural cmod natural că ă poate fi calculatpoate fi calculatăă,,

poate fi executată și poate fi executată și pe o mape o mașșininăă Turing. Turing.

ÎÎn consecinn consecințăță, o , o funcfuncțțieie se nume se numeșște te calculabilcalculabilăă dac dacăă poate fi calculat poate fi calculatăă pe o pe o mamașșininăă Turing Turing șși necalculabili necalculabilăă îîn restn rest..

Turing afirma cTuring afirma căă aceast aceastăă ma mașșininăă, , denumitdenumităă ma mașșina Turing, este ina Turing, este

capabila sa cuprinda tot ce s-ar putea capabila sa cuprinda tot ce s-ar putea intelege prin “intelege prin “metoda bine definitametoda bine definita” din ” din problema problema ddeciziei, “metoda” care defineeciziei, “metoda” care defineșște te de fapt un de fapt un algoritmalgoritm..

Se cuvine Se cuvine de de menţionat faptul că ideea de a menţionat faptul că ideea de a descrie un program folosind un limbaj (şi nu prin descrie un program folosind un limbaj (şi nu prin conexiuni între unităţi funcţionale) este mai conexiuni între unităţi funcţionale) este mai veche; veche;

ÎÎn 1936 Alan Turing folosise noţiunea de n 1936 Alan Turing folosise noţiunea de ``maşină Turing universală''``maşină Turing universală'' pentru a descrie un pentru a descrie un calculator universal, care poate executa orice calculator universal, care poate executa orice program. Programele erau stocate în memoria program. Programele erau stocate în memoria calculatorului, reprezentate ca şiruri de numere. calculatorului, reprezentate ca şiruri de numere.

DacDacăă g gîîndirea umanndirea umanăă nu este o ma nu este o mașșininăă Turing, atunci nu este algoritmicTuring, atunci nu este algoritmicăă șși nu se i nu se bazeazbazeazăă pe sisteme formale. Ca atare ea pe sisteme formale. Ca atare ea NU este supusNU este supusăă limit limităărilor sistemelor rilor sistemelor formale formale ..

ÎÎn aceste condin aceste condițții orice calculator (maii orice calculator (mașșina ina Turing) va puteTuring) va puteaa cel mult simula cel mult simula inteligeninteligențța umana, dar NU va putea sa umana, dar NU va putea săă o o egaleze. egaleze.

Mulţumim pentru atenţie!