Проблема разрешения

Проблема разрешения (нем. Entscheidungsproblem) — задача из области оснований математики, сформулированная Давидом Гильбертом в 1928 году: найти алгоритм, который бы принимал в качестве входных данных описание любой проблемы разрешимости (формального языка и математического утверждения « $S$ » на этом языке) — и, после конечного числа шагов, останавливался бы и выдавал один из двух ответов: «Истина!» или «Ложь!», — в зависимости от того, истинно или ложно утверждение « $S$ ». Ответ не требует обоснований, но должен быть верным.

Такой алгоритм мог бы, к примеру, подтвердить гипотезу Гольдбаха и гипотезу Римана несмотря на то, что доказательства (и опровержения) пока неизвестны. Нерешаемость проблемы разрешения (неразрешимость множества истинных формул арифметики) для языка арифметики, содержащего «равенство», «сложение» и «умножение», является следствием неарифметичности этого множества. Неарифметичность является следствием теоремы Тарского «о невыразимости понятия истинности в языке средствами того же языка»^[1].

В 1936 году — Алонзо Чёрч и независимо от него Алан Тьюринг опубликовали работы, в которых показали, что не существует алгоритма для определения истинности утверждений арифметики, а поэтому и более общая проблема разрешения также не имеет решения. Этот результат получил название: «теорема Чёрча — Тьюринга».

См. также

Теорема Геделя о неполноте

Примечания

↑ В. А. Успенский, А. Л. Семёнов Теория алгоритмов: основные открытия и приложения, М., Наука, 1987, 288 c., 2.3 Приложения к математической логике: анализ формализованных языков логики и арифметики

Литература

Alonzo Church. An unsolvable problem of elementary number theory // American Journal of Mathematics. — 1936. — Vol. 58. — P. 345—363. — doi:10.2307/2371045.
Alonzo Church. A note on the Entscheidungsproblem // Journal of Symbolic Logic. — 1936. — Vol. 1. — P. 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
Эдельман С.Л. Математическая логика. — М.: Высшая школа, 1975. — 176 с.

[1] В. А. Успенский, А. Л. Семёнов Теория алгоритмов: основные открытия и приложения, М., Наука, 1987, 288 c., 2.3 Приложения к математической логике: анализ формализованных языков логики и арифметики

[1]