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

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

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

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

$\chi (a)=\{\begin{array}{cc}0,& \text{if}(Ex)T(a,a,x)\\ 1,& \text{else}\end{array}$

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

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

См. также

• Теорема Геделя о неполноте
• Теорема Тарского о невыразимости истины

Литература

• Шаблон:Книга