Echivalența Turing

Această intrare sau secțiune despre limbaje de programare nu menționează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .

Echivalența Turing este proprietatea modelelor de calcul care au aceeași putere de calcul ca o mașină universală Turing ( MdTu ).

Un model care are aceeași putere de calcul ca un MdTu se numește echivalent Turing sau Turing complet .

Modele Turing echivalente cunoscute

Cele mai cunoscute modele de calcul echivalente 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, cum ar fi mașina URM ;
• calculul predicatelor (vezi teorema completitudinii lui Gödel și teorema Bisericii ).

Chiar și cele mai comune limbaje de programare , atât imperative , cât și funcționale , sunt echivalente Turing.

Deoarece compilarea unui program necesită utilizarea unor construcții condiționale, cicluri și memorie nelimitate, un limbaj de uz general echipat cu astfel de constructe (și, prin urmare, echivalentul lui Turing) vă permite să scrieți un compilator . Acest lucru a generat obiceiul de a lua în considerare un limbaj generic ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">L</span></span>}}${\ displaystyle L} ca echivalentul Turing atunci când este posibil să scrieți un compilator de programe ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">L</span></span>}}${\ displaystyle L} folosind ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">L</span></span>}}${\ displaystyle L} la fel. În realitate nu este necesar să se aștepte utilizarea unui limbaj într-un astfel de proiect: este suficient ca acesta să prezinte unele proprietăți elementare, așa cum se vede prin modelele Turing echivalente mai simple (de exemplu, mașinile de registru elementar).

Exemple de modele de calcul care sunt mai puțin puternice decât un MdT universal sunt expresiile regulate , automatele de stare finită și mașinile care se termină întotdeauna .

Curiozitate

• Jocul vieții este considerat echivalentul lui Turing. ^{[1] [2]}
• În jocul video Factorio este posibil să joci Jocul Vieții , prin urmare este considerat și echivalent Turing. ^{[3] [4] [5]}

Notă

Elemente conexe

• Teza Bisericii-Turing

Portal IT

Portalul de matematică