Churchova-Turingova věta

Church-Turingova věta  je tvrzení o absenci algoritmu , který řeší problém řešení . Slouží k prokázání neřešitelnosti aritmetiky přirozených čísel [1] . Poprvé ji formuloval a dokázal v roce 1936 Alonzo Church [2] [3] (spolu s Churchovou tezí ); ve stejném roce, ale o něco později, tento výsledek nezávisle získal Alan Turing [4] [5] .

Formulace

Predikát[ objasnit ] je nerozhodnutelné, tj. funkce:

nevypočitatelný.

Tato formulace používá pojem Turingovy vyčíslitelnosti.

Viz také

Poznámky

  1. ↑ Matematická logika, 1973 , str. 297.
  2. ↑ Kostel, Alonzo. An Unsolvable Problem of Elementary Number Theory  (anglicky)  // American Journal of Mathematics  : journal. - 1936. - Sv. 58 . - str. 345-363 . - doi : 10.2307/2371045 . — .
  3. ↑ Kostel, Alonzo. A note on the Entscheidungsproblem  (neopr.)  // Journal of Symbolic Logic. - 1936. - T. 1 . - S. 40-41 .
  4. ↑ Turing A. On Computable Numbers, with the Application to the Entscheidungsproblem  // Proceedings of the London Mathematical Society - London Mathematical Society , 1937. - Vol. s2-42, Iss. 1. - S. 230-265. — ISSN 0024-6115 ; 1460-244X – doi:10.1112/PLMS/S2-42.1.230
  5. ↑ Turing A. M. On Computable Numbers, with Application to Entscheidungsproblem. A Correction  (anglicky) // Proceedings of the London Mathematical Society - London Mathematical Society , 1938. - Vol. s2-43, Iss. 6. - S. 544-546. — ISSN 0024-6115 ; 1460-244X – doi:10.1112/PLMS/S2-43.6.544

Literatura