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