Interested Article - Теорема Чёрча — Тьюринга

Теоре́ма Чёрча — Тью́ринга — утверждение об отсутствии алгоритма , решающего проблему разрешения . Используется при доказательстве неразрешимости арифметики натуральных чисел . Впервые была сформулирована и доказана в 1936 году Алонзо Чёрчем (вместе с тезисом Чёрча ); в том же году, но несколько позже этот результат независимо получил Алан Тьюринг .

Формулировка

Предикат $(Ex)T(a,a,x)$ ^{[

уточнить

]} неразрешим, то есть функция:

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

невычислима.

Данная формулировка использует понятие вычислимости по Тьюрингу.

, с. 297.
Church, Alonzo. (англ.) // American Journal of Mathematics : journal. — 1936. — Vol. 58 . — P. 345—363 . — doi : . — JSTOR .
Church, Alonzo. A note on the Entscheidungsproblem (неопр.) // (англ.) ( . — 1936. — Т. 1 . — С. 40—41 .
Turing A. (англ.) // — London Mathematical Society , 1937. — Vol. s2-42, Iss. 1. — P. 230—265. — ISSN ; ; —
Turing A. M. (англ.) // — London Mathematical Society , 1938. — Vol. s2-43, Iss. 6. — P. 544—546. — ISSN ; ; —