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

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

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

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

χ (a) = {\begin{matrix} 0, & if (E x) T (a, a, x) \\ 1, & else \end{matrix}

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

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