Church-Turing tétel

A Church-Turing-tétel egy olyan állítás , amely a felbontási problémát megoldó algoritmus hiányára vonatkozik . A természetes számok aritmetikája megoldhatatlanságának bizonyítására szolgál [1] . Először Alonzo Church fogalmazta meg és bizonyította 1936 -ban [2] [3] (együtt Church tézisével ); ugyanebben az évben, de valamivel később ezt az eredményt függetlenül érte el Alan Turing [4] [5] .

Megfogalmazás

Állítmány $(Pl.)T(a,a,x)$ A [ clarify ] eldönthetetlen, azaz a függvény:

\chi (a)={\begin{cases}0,&{\mbox{if}}(Ex)T(a,a,x)\\1,&{\mbox{else}}\end{cases} }

kiszámíthatatlan.

Ez a megfogalmazás a Turing-számíthatóság fogalmát használja.

↑ Matematikai logika, 1973 , p. 297.
↑ Templom, Alonzo. Az elemi számelmélet megoldhatatlan problémája (angol) // American Journal of Mathematics : folyóirat. - 1936. - 1. évf. 58 . - P. 345-363 . - doi : 10.2307/2371045 . — .
↑ Templom, Alonzo. Megjegyzés az Entscheidungsproblem- hez (neopr.) // Journal of Symbolic Logic. - 1936. - T. 1 . - S. 40-41 .
↑ Turing A. On Computable Numbers, with an Appliance to the Entscheidungsproblem // Proceedings of the London Mathematical Society - London Mathematical Society , 1937. - Vol. s2-42, Iss. 1. - P. 230-265. — ISSN 0024-6115 ; 1460-244X - doi:10.1112/PLMS/S2-42.1.230
↑ Turing A. M. A kiszámítható számokról, az Entscheidungsprobléma alkalmazásával. A Correction (angol) // Proceedings of the London Mathematical Society - London Mathematical Society , 1938. - Vol. s2-43, Iss. 6. - P. 544-546. — ISSN 0024-6115 ; 1460-244X - doi:10.1112/PLMS/S2-43.6.544