Теорема Чёрча — Тьюринга
Теоре́ма Чёрча — Тью́ринга — утверждение об отсутствии
.Формулировка
Предикат [уточнить] неразрешим, то есть функция:
невычислима.
Данная формулировка использует понятие вычислимости по Тьюрингу.
См. также
- Теорема Геделя о неполноте
- Теорема Тарского о невыразимости истины
Примечания
- ↑ Математическая логика, 1973, с. 297.
- doi:10.2307/2371045. —.
- ↑ Church, Alonzo. A note on the Entscheidungsproblem (неопр.) // Journal of Symbolic Logic[англ.]. — 1936. — Т. 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. s2-42, Iss. 1. — P. 230—265. — ISSN 0024-6115; 1460-244X; 0024-6115 — 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; 0024-6115 — doi:10.1112/PLMS/S2-43.6.544
Литература
- Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.
слишком короткая. }}. (9 марта 2023) |