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

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

В математике проблемой разрешения (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.