Church-Turing-sætning

Church-Turing-sætningen er et udsagn om fraværet af en algoritme , der løser opløsningsproblemet . Bruges til at bevise uopløseligheden af aritmetikken af naturlige tal [1] . Den blev først formuleret og bevist i 1936 af Alonzo Church [2] [3] (sammen med Churchs afhandling ); samme år, men noget senere, blev dette resultat uafhængigt opnået af Alan Turing [4] [5] .

Ordlyd

Prædikat $(Ex)T(a,a,x)$ [ klargør ] er uafgørlig, dvs. funktionen:

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

uberegnelig.

Denne formulering bruger begrebet Turing-beregnelighed.

↑ Mathematical Logic, 1973 , s. 297.
↑ Kirke, Alonzo. An Unsolvable Problem of Elementary Number Theory (engelsk) // American Journal of Mathematics : tidsskrift. - 1936. - Bd. 58 . - S. 345-363 . - doi : 10.2307/2371045 . — .
↑ Kirke, Alonzo. En note om Entscheidungsproblemet (neopr.) // Journal of Symbolic Logic. - 1936. - T. 1 . - S. 40-41 .
↑ Turing A. On Computable Numbers, with an 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 beregnelige tal, med en applikation til Entscheidungsproblemet. A Correction (engelsk) // 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