Открыть главное меню

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

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

ФормулировкаПравить

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

 

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

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

ПримечанияПравить

ЛитератураПравить

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