Теоре́ма Чёрча — Тью́ринга — утверждение об отсутствии алгоритма, решающего проблему разрешения. Используется при доказательстве неразрешимости арифметики натуральных чисел[1]. Впервые была сформулирована и доказана в 1936 году Алонзо Чёрчем[2][3] (вместе с тезисом Чёрча); в том же году, но несколько позже этот результат независимо получил Алан Тьюринг[4][5].
Формулировка
Предикат [уточнить] неразрешим, то есть функция:
невычислима.
Данная формулировка использует понятие вычислимости по Тьюрингу.
Примечания
- ↑ Математическая логика, 1973, с. 297.
- ↑ Church, Alonzo (1936). “An Unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics. 58: 345—363. DOI:10.2307/2371045. JSTOR 2371045.
- ↑ Church, Alonzo (1936). “A note on the Entscheidungsproblem”. Journal of Symbolic Logic. 1: 40—41.
- ↑ Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society — London Mathematical Society, 1937. — Vol. 42. — P. 230–265. — ISSN 0024-6115; 1460-244X — doi:10.1112/PLMS/S2-42.1.230
- ↑ Turing A. M. On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction // Proceedings of the London Mathematical Society — London Mathematical Society, 1938. — Vol. s2-43, Iss. 6. — P. 544–546. — ISSN 0024-6115; 1460-244X — doi:10.1112/PLMS/S2-43.6.544
Литература
- Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .