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

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

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

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

Примечания[править | править вики-текст]

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

Литература[править | править вики-текст]

  • Alonzo Church, «An unsolvable problem of elementary number theory», American Journal of Mathematics, 58 (1936), pp 345—363
  • Alonzo Church, «A note on the Entscheidungsproblem», Journal of Symbolic Logic, 1 (1936), pp 40-41.