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

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

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