Auto-aplicabilitate
Autoaplicabilitatea în teoria algoritmilor este proprietatea unui algoritm de a completa cu succes date care sunt o înregistrare formală a aceluiași algoritm.
Problema recunoașterii autoaplicabilității este de nerezolvată din punct de vedere algoritmic și se rezumă la găsirea unui algoritm care să permită, într-un număr finit de pași în notația formală a unui algoritm, să se afle dacă este autoaplicabil sau nu. Deși această problemă este oarecum artificială și nu are un interes independent, ea este adesea folosită pentru a dovedi insolubilitatea altor probleme mai complexe. Metoda generală pentru astfel de inferențe este aceea că din ipoteza existenței unui algoritm care rezolvă o anumită problemă se deduce existența unui algoritm care rezolvă problema recunoașterii autoaplicabilității.
Dovada indecidibilității algoritmice
Dovada prin contradictie . Să presupunem că există un algoritm care recunoaște autoaplicabilitatea. Pe baza tezei Turing , există și o mașină Turing care implementează acest algoritm. Să desemnăm o astfel de mașină ca . Pe banda sa, un program codat al unei alte mașini Turing este introdus într-un fel, iar după lucru, datele introduse sunt procesate într-un cuvânt dacă programul original era autoaplicabil sau într-un cuvânt dacă nu era autoaplicabil.
În a doua etapă, modificăm ușor mașina, astfel încât să proceseze în continuare programe neaplicabile în , și bucle pe programele auto-aplicabile , adică nu este aplicabilă acestora. Este foarte ușor să faci o astfel de transformare - după ce a scris un cuvânt , mașina nu își termină munca, dar continuă să-l scrie la nesfârșit pe bandă. Să desemnăm această mașină ca . Existența unei astfel de mașini duce la o contradicție, deoarece nu poate fi nici autoaplicabilă, nici neautoaplicabilă. Într-adevăr, dacă este autoaplicabil, atunci este aplicabil la propria sa notație. Dar, conform construcției mașinii, acest lucru indică doar că nu este autoaplicabil. Dacă nu este autoaplicabil, atunci, prin construcție, este aplicabil propriei evidențe, deoarece este aplicabil oricărei înregistrări a unei mașini care nu se aplică automat. Dar asta înseamnă doar că este auto-aplicabil. Pornind de la aceasta, se face o concluzie despre imposibilitatea construirii unei mașini , de atunci ar fi ușor să se obțină de la ea .
Literatură
- V. I. IGOSHIN Logica matematică și teoria algoritmilor. - M . : Academia, 2004. - S. 369-370. — 448 p. - 5100 de exemplare. — ISBN 5-7695-1363-2 .
- A. L. Semionov. Programe autoaplicabile // Matematica textelor . - 2002. - 16 p. - 3000 de exemplare. — ISBN 5-94057-006-2 .
- E. M. Ivanov. Argumentul lui Gödel // Despre problema „computabilității” funcției conștiinței .
- Mihail Hazewinkel. Indecidibilitate // Enciclopedia de matematică . - Berlin: Springer Olanda, 2002. - ISBN 1-4020-0609-8 . (Engleză)
- Arto Salomaa. 4.3 Teorema recursiunii și rezultatele de bază a indecidibilității // Calcul și automatele . - Cambridge University Press, 1985. - V. 25. - S. 90. - 284 p. — ISBN 9780521302456 . (Engleză)