Teza Bisericii-Turing
În teoria calculabilității, teza Bisericii-Turing este o ipoteză care afirmă: „Dacă o problemă este uman calculabilă, atunci va exista o mașină Turing capabilă să o rezolve (adică să o calculeze )”. Mai formal, putem spune că clasa funcțiilor calculabile coincide cu cea a funcțiilor calculabile de către o mașină Turing.
Istorie
Teza Church-Turing poartă numele matematicienilor Alonzo Church și Alan Turing , care au introdus-o între anii 1930 și 1940 . Activitatea celor două pe această temă a început să rezolve celebrul Entscheidungsproblem , sau problema de decizie ridicată de David Hilbert . În esență, Hilbert s-a întrebat dacă ar putea exista un algoritm care să poată decide adevărul sau falsitatea oricărei afirmații matematice. Pentru a aborda problema, Church și Turing s-au preocupat de definirea riguroasă a conceptului de algoritm. În mod independent și pe căi foarte diferite, au ajuns la aceleași rezultate. Church a publicat în 1936 un tratat în care a definit calculul lambda , iar în același an, dar câteva luni mai târziu, Turing a publicat un eseu în care a introdus conceptul de mașină Turing , pe care apoi l-a folosit pentru a răspunde la problema Entscheidungs . Cei doi matematicieni au ajuns la concluzia că sistemele automate de calcul (și altele care au continuat să iasă la iveală, precum cel propus de americanul Emil Post ) pe care le propuseseră erau echivalente din punct de vedere al puterii de calcul. Rezultă că fiecare dintre aceste instrumente întruchipează chiar conceptul de algoritm .
Funcții recursive parțiale
Clasa de funcții care poate fi calculată cu un formalism, cum ar fi mașina Turing, coincide cu clasa de funcții care pot fi calculate de către mașina RAM sau de mașina RASP . Mai mult, această clasă coincide cu clasa de funcții calculabile prin diferite formalisme ( Pascal , C , ...). Independența față de formalisme face ca această clasă de funcții să fie funcții recursive parțiale .
Ceea ce a afirmat teza Church-Turing se aplică în mod evident și pentru toate modelele de calcul echivalente cu mașinile Turing , pentru care, de exemplu, o formulare echivalentă a tezei înseamnă că funcțiile recursive și funcțiile calculabile sunt același lucru .
Teza Bisericii-Turing este acum acceptată universal, dar nu poate fi dovedită.
Teza extinsă Biserică-Turing
Având în vedere un program care poate fi rezolvat cu un formalism și cu o complexitate limitată de un polinom, adică , compilând programul într-un alt formalism se poate observa că complexitatea nu se schimbă.
Modele de calcul echivalente
Cele mai cunoscute modele de calcul echivalente Turing , care calculează aceleași funcții ca o mașină Turing sunt:
- funcții recursive ;
- Modelul lui Kleene bazat pe ecuații funcționale;
- Calculul lambda al Bisericii;
- logica combinatorie ;
- algoritmii normali Markov ;
- sistemele combinatorii de Post ;
- mașini de înregistrare primare ;
- calculul predicatelor (vezi teorema completitudinii lui Godel și teorema Bisericii ).
Chiar și cele mai comune limbaje de programare , atât imperative , cât și funcționale, sunt echivalente Turing. În special, un limbaj este echivalentul lui Turing atunci când este capabil să se compileze .
Exemple de modele de calcul care sunt mai puțin puternice decât o mașină Turing sunt expresiile regulate , automatele în stare finită și mașinile care se termină întotdeauna .
În concluzie, putem spune că niciun formalism mai puternic decât mașina Turing nu este cunoscut în termeni de calcul. Deci, tot ceea ce nu poate fi calculat de TM nu poate fi calculat de niciun alt formalism cunoscut de noi.
Bibliografie
- Giorgio Ausiello, Fabrizio d'Amore, Giorgio Gambosi; FrancoAngeli Editor: Limbi, modele, complexitate (2003) ( ISBN 88-464-4470-1 )
- Brainerd, WS, Landweber, LH (1974), Theory of Computation , Wiley, ISBN 0-471-09585-0
Alte proiecte
-
Wikimedia Commons conține imagini Church-Turing sau alte fișiere
| Controlul autorității | GND (DE) 4444529-5 · BNF (FR) cb162445653 (data) |
|---|
