Teză Church-Turing

Teza Church-Turing si istoria ei

Pana in present există mai multe formulări echivalente ale tezei Church-Turing. Această teză fara sa fie o teoremă demonstrată afirmă că Masina Turing Universală (MTU) este un model matematic suficient de general pentru orice procedură efectivă de calcul, respectiv MTU poate fi programată pentru orice este calculabil (computabil).

Teza Church-Turing este adesea înţeleasa greşit, în special în ultimele scrieri ale filosofiei gandirii.

Teza Church-Turing se referă la noţiunea de metodă efectivă sau metoda mecanică intalnită în logică şi matematică. Termenii "efectiv" şi "mecanic" comporta in acest context un alt inteles decat cel obisnuit. O metodă, sau o procedura M, prin care se urmareste obtinerea unui rezultat este numită "efectiva" sau "mecanica" doar în cazul în care:

- Procedura M este stabilită în funcţie de un număr finit de instrucţiuni exacte (fiecare instrucţiune fiind exprimată printr-un număr finit de simboluri);

- Procedura M va produce rezultatul dorit dupa parcurgerea unui număr finit de paşi (excluzand eventualele erori);

- Procedura M poate fi dusa la bun sfarsit atat in practica cat si in teorie de către un om fara ajutorul unei masini;

- Procedura M nu solicita din punct de vedere intelectual in nici un fel persoana care o indeplineste.

Un bine-cunoscut exemplu de metoda efectiva este testul tautologic.

În practică testul e ineficienta pentru formule care conţin un număr mare de variabile propozitionale, dar in principiu insa, s-ar putea aplica usor la orice formulă de calcul propositional, in cazul in care se dispune de timp si tenacitate pentru asta.

Afirmatia cum ca există o metodă efectiva pentru a obtine anumite rezultate este adesea exprimata prin declararea existentei metodei efective pentru obtinerea valorilor in cazul anumitor functii matematice.

De exemplu, faptul ca exista o metoda efectiva pentru determinarea faptului ca orice formula a calculului propozitiona este o tautologie – ex: metoda tabelei de adevar – este exprimat in functia verbala spunand ca exista o metoda efectiva pentru obtinerea valorilor unei functii, numite T, al carui domeniu este setul de formule ale calculului propozitional si ale carei valori pentru orice formula x, scrisa T(x) este 1 sau 0, in functie de intrebarea este x sau nu tautologie.

Noţiunea de metodă efectiva este una informala iar încercările de a caracteriza eficienţa sunt lipsite de rigoare deoarece conditia ca metoda sa nu solicite intelectual utilizatorul nu este indeplinita.

Una dintre realizările lui Turing pusa pe hartie in anul 1936 a fost aceea de a prezenta oficial un predicat exact formal care sa inlocuiasca predicatul informal "poate fi calculată printr-o metodă efectivă".

Church a facut la fel in acelasi an 1936. Variantele de inlocuire a predicatelor propuse de Turing şi, respectiv de Church erau foarte diferite in aparenta dar acestea s-au dovedit a fi echivalente, în sensul că amandoua reliefeaza acelaşi set de funcţii matematice.

Teza Church-Turing reprezinta afirmarea faptului ca acest set mai-sus mentionat conţine fiecare funcţie ale cărei valori pot fi obţinute printr-o metodă care sa îndeplineasca condiţiile de mai sus de eficienţa. (În mod evident, dacă exista functii al caror predicat informal ar fi adevarat, fara ca predicatul formal sa fie adevarat, atunci acesta din urma ar fi mai putin general decat cel informal si deci nu ar putea fi folosit sa il inlocuiasca pe primul).

Atunci cand teza este prezentata folosindu-se conceptul propus oficial de către Turing, este cel mai potrivit ca referirea la aceasta teza sa se faca ca fiind teza Turing; aceeasi regula ar trebui aplicata, si in cazul lui Church.

Conceptul formal propus de Turing este acela de computabilitate a masinii Turing. El sustinea ca ori de cate ori exista o metoda efectiva de a obtine valori pentru functii matematice, funcţia poate fi calculata de către maşină Turing.

Afirmatie de altfel este dovedita dat fiind fapul ca masina Turing în sine este o specificatie de metodă eficientă: cu minim efort intelectual, orice fiinta umana poate lucra urmand instrucţiunile din program şi indeplinind operaţiunile necesare. Dacă teza Turing este corectă, atunci discutiile despre existenţa şi non-existenţa unor metode efective pot fi înlocuite atat în domeniul matematicii cat si in cel al logicii de discutii legate de existenţa sau non-existenţa unor programe ale masinii Turing.

Turing si-a facut cunoscuta teza de nenumarate ori, gradul de rigoare variind cu prilejul expunerilor sale. Una dintre cele mai accesibile formulari ale sale este urmatoarea:

Teza Turing:

LCMs [logical computing machines: aceasta este expresia folita de Turing pentru maşinile Turing] pot face orice ar putea fi descris ca fiind "empiric" sau "pur mecanic". (Turing 1948)

Calculabilitate si complexitate - Fac. Mate-Info - Proiect anul II - IDD