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

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

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

См. также

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

Примечания

Литература

• Alonzo Church. // American Journal of Mathematics. — 1936. — Vol. 58. — P. 345—363. — doi : .
• Alonzo Church. A note on the Entscheidungsproblem // Journal of Symbolic Logic. — 1936. — Vol. 1. — P. 40—41.
• Turing A. (англ.) // — London Mathematical Society , 1937. — Vol. s2-42, Iss. 1. — P. 230—265. — ISSN ; ; —
• Turing A. M. (англ.) // — London Mathematical Society , 1938. — Vol. s2-43, Iss. 6. — P. 544—546. — ISSN ; ; —
• Эдельман С.Л. Математическая логика. — М. : Высшая школа, 1975. — 176 с.