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

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

Предикат $(Ex)T(a,a,x)$ неразрешим, то есть функция:

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

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

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

Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.

Формулировка
См. также
Примечания
Литература