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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

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

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

См. также

[править | править код]

Примечания

[править | править код]
  1. ↑ Математическая логика, 1973, с. 297.
  2. ↑ Church, Alonzo. An Unsolvable Problem of Elementary Number Theory (англ.) // American Journal of Mathematics : journal. — 1936. — Vol. 58. — P. 345—363. — doi:10.2307/2371045. — JSTOR 2371045.
  3. ↑ Church, Alonzo. A note on the Entscheidungsproblem // Journal of Symbolic Logic[англ.]. — 1936. — Т. 1. — С. 40—41.
  4. ↑ Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem, On Computable Numbers, with an Application to the Entscheidungsproblem (англ.) // Proceedings of the London Mathematical Society — London Mathematical Society, 1936. — Vol. s2-42, Iss. 1. — P. 230—265. — ISSN 0024-6115; 1460-244X; 0024-6115 — doi:10.1112/PLMS/S2-42.1.230
  5. ↑ 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; 0024-6115 — doi:10.1112/PLMS/S2-43.6.544

Литература

[править | править код]
  • Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.
Эта статья слишком короткая.
Пожалуйста, дополните её ещё хотя бы несколькими предложениями и уберите это сообщение. Если статья останется недописанной, она может быть выставлена к удалению. Для указания на продолжающуюся работу над статьёй используйте шаблон {{subst:Редактирую}}.
Администраторам и подводящим итоги: эта пометка оставлена 2014-07-14. Просьба очень короткие заготовки статей ранее чем через два дня после создания не удалять. (14 июля 2014)
Источник — https://ru.wikipedia.org/w/index.php?title=Теорема_Чёрча_—_Тьюринга&oldid=149591003