Church-Turing-sats

Church-Turing-satsen är ett uttalande om frånvaron av en algoritm som löser upplösningsproblemet . Används för att bevisa olösbarheten av aritmetiken av naturliga tal [1] . Den formulerades och bevisades först 1936 av Alonzo Church [2] [3] (tillsammans med Churchs avhandling ); samma år, men något senare, erhölls detta resultat oberoende av Alan Turing [4] [5] .

Formulering

Predikat $(Ex)T(a,a,x)$ [ förtydliga ] är obestämbar, dvs funktionen:

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

oberäkningsbar.

Denna formulering använder begreppet Turing beräkningsbarhet.

↑ Mathematical Logic, 1973 , sid. 297.
↑ Kyrka, Alonzo. An Unsolvable Problem of Elementary Number Theory (engelska) // American Journal of Mathematics : journal. - 1936. - Vol. 58 . - s. 345-363 . - doi : 10.2307/2371045 . — .
↑ Kyrka, Alonzo. En anteckning om Entscheidungsproblemet (neopr.) // Journal of Symbolic Logic. - 1936. - T. 1 . - S. 40-41 .
↑ Turing A. On Computable Numbers, with a 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
↑ Turing A. M. om beräkningsbara nummer, med en tillämpning på Entscheidungsproblemet. A Correction (engelska) // 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