В теории вычислимости и теории сложности вычислений неразрешимая проблема — это проблема решения , для которой оказывается невозможным построить алгоритм , который всегда приводит к правильному ответу «да» или «нет». Примером может служить проблема остановки : можно доказать, что не существует алгоритма, который правильно определяет, останавливается ли произвольная программа в конечном итоге при запуске. [1]
Проблема принятия решения — это вопрос, на который для каждого входного сигнала в некотором бесконечном наборе входных данных можно получить ответ «да» или «нет». [2] . Эти входные данные могут быть числами (например, проблема принятия решения «является ли входное число простым числом?») или другими значениями другого типа, такими как строки формального языка .
Формальное представление проблемы принятия решения представляет собой подмножество натуральных чисел . Для задач решения натуральных чисел набор состоит из тех чисел, на которые задача решения отвечает «да». Например, проблема принятия решения: «Является ли вход четным?» формализуется как множество четных чисел. Задача принятия решения, входные данные которой состоят из строк или более сложных значений, формализуется как набор чисел, которые посредством определенной нумерации Гёделя соответствуют входным данным, удовлетворяющим критериям задачи принятия решения.
Проблема решения A называется разрешимой или эффективно разрешимой, если формализованное множество A является рекурсивным множеством . В противном случае A называется неразрешимым. Задача называется частично разрешимой, полуразрешимой, разрешимой или доказуемой, если A — рекурсивно перечислимое множество . [номер 1]
В теории вычислимости проблема остановки — это проблема решения , которую можно сформулировать следующим образом:
Алан Тьюринг доказал в 1936 году, что общий алгоритм , работающий на машине Тьюринга и решающий проблему остановки для всех возможных пар программа-вход, обязательно не может существовать. Следовательно, проблема остановки неразрешима для машин Тьюринга.
Идеи, возникающие в теоремах Гёделя о неполноте, очень похожи на концепции, возникающие в проблеме остановки, и доказательства очень похожи. Фактически, более слабая форма Первой теоремы о неполноте является простым следствием неразрешимости проблемы остановки. Эта более слабая форма отличается от стандартной формулировки теоремы о неполноте тем, что утверждает, что аксиоматизация натуральных чисел, которая является одновременно полной и правильной , невозможна. «Звуковая» часть является ослабляющей: она означает, что мы требуем от рассматриваемой аксиоматической системы доказательства только истинных утверждений о натуральных числах. Поскольку надежность подразумевает последовательность , эту более слабую форму можно рассматривать как следствие сильной формы. Важно отметить, что утверждение стандартной формы Первой теоремы Гёделя о неполноте совершенно не заботится об истинности утверждения, а касается только вопроса о том, можно ли найти его с помощью математического доказательства .
Более слабая форма теоремы может быть доказана из неразрешимости проблемы остановки следующим образом. [3] Предположим, что у нас есть обоснованная (и, следовательно, непротиворечивая) и полная аксиоматизация всех истинных логических утверждений первого порядка о натуральных числах . Затем мы можем построить алгоритм, который перечисляет все эти утверждения. Это означает, что существует алгоритм N ( n ), который по натуральному числу n вычисляет истинное логическое утверждение первого порядка о натуральных числах, и что для всех истинных утверждений существует хотя бы одно n такое, что N ( n ) дает это утверждение. Теперь предположим, что мы хотим решить, остановится ли алгоритм с представлением a на входе i . Мы знаем, что это утверждение можно выразить с помощью логического утверждения первого порядка, скажем, H ( a , i ). Поскольку аксиоматизация завершена, отсюда следует, что либо существует n такое, что N ( n ) = H ( a , i ), либо существует n ′ такое, что N ( n ′ ) = ¬ H ( a , i ). Таким образом, если мы будем перебирать все n до тех пор, пока не найдем H ( a , i ) или его отрицание, мы всегда остановимся, и, более того, ответ, который он нам даст, будет истинным (по обоснованности). Это означает, что это дает нам алгоритм для решения проблемы остановки. Поскольку мы знаем, что такого алгоритма не может быть, из этого следует, что предположение о том, что существует непротиворечивая и полная аксиоматизация всех истинных логических утверждений первого порядка о натуральных числах, должно быть ложным.
Неразрешимые проблемы могут быть связаны с разными темами, такими как логика , абстрактные машины или топология . Поскольку неразрешимых задач несчетно много, [nb 2] любой список, даже бесконечной длины , обязательно неполный.
В современном использовании слово «неразрешимый» имеет два различных значения. Первый из них — это смысл, используемый по отношению к теоремам Гёделя, а именно: утверждение, которое не является ни доказуемым, ни опровержимым в определенной дедуктивной системе . Второй смысл используется по отношению к теории вычислимости и применяется не к утверждениям, а к задачам решения , которые представляют собой счетное бесконечное множество вопросов, каждый из которых требует ответа «да» или «нет». Такая задача называется неразрешимой, если не существует вычислимой функции , которая правильно отвечает на каждый вопрос в наборе задач. Связь между этими двумя вопросами заключается в том, что если проблема принятия решения неразрешима (в теоретическом смысле рекурсии), то не существует непротиворечивой, эффективной формальной системы , которая доказывает для каждого вопроса А в задаче либо «ответ на А — да», либо «ответ на А — да». ответ на вопрос А – нет».
Из-за двух значений слова «неразрешимый» термин « независимый» иногда используется вместо слова «неразрешимый» в смысле «ни доказуемого, ни опровержимого». Однако использование слова «независимый» также неоднозначно. Это может означать просто «недоказуемо», оставляя открытым вопрос о том, может ли независимое утверждение быть опровергнуто.
Неразрешимость утверждения в конкретной дедуктивной системе сама по себе не решает вопрос о том, является ли истинностное значение утверждения четко определенным или может ли оно быть определено другими средствами. Неразрешимость подразумевает только то, что конкретная рассматриваемая дедуктивная система не доказывает истинность или ложность утверждения. Существуют ли так называемые «абсолютно неразрешимые» утверждения, истинностное значение которых никогда не может быть известно или плохо определено, является спорным вопросом среди различных философских школ .
Одной из первых проблем, предположительно неразрешимых во втором смысле этого слова, была проблема слов для групп , впервые поставленная Максом Деном в 1911 году, которая задавалась вопросом, существует ли конечно представленная группа , для которой не существует алгоритма, позволяющего определить, является ли два слова эквивалентны. Это было показано в 1952 году.
Совместная работа Гёделя и Пауля Коэна дала два конкретных примера неразрешимых утверждений (в первом смысле этого слова): гипотеза континуума не может быть ни доказана, ни опровергнута в ZFC (стандартная аксиоматизация теории множеств ), а аксиома выбор нельзя ни доказать, ни опровергнуть в ZF (что является всеми аксиомами ZFC, кроме аксиомы выбора). Эти результаты не требуют теоремы о неполноте. Гёдель доказал в 1940 году, что ни одно из этих утверждений не может быть опровергнуто ни в теории множеств ZF, ни в теории множеств ZFC. В 1960-х годах Коэн доказал, что ни то, ни другое невозможно доказать с помощью ZF, а гипотезу континуума нельзя доказать с помощью ZFC.
В 1970 году русский математик Юрий Матиясевич показал, что Десятая проблема Гильберта , поставленная в 1900 году как вызов математикам следующего столетия, неразрешима. Задача Гильберта заключалась в поиске алгоритма, который находит все решения диофантового уравнения . Диофантово уравнение — это более общий случай Великой теоремы Ферма ; мы ищем целые корни многочлена от любого числа переменных с целыми коэффициентами . Поскольку у нас есть только одно уравнение, но п переменных, существует бесконечно много решений (и их легко найти) на комплексной плоскости ; однако проблема становится невозможной, если решения ограничиваются только целочисленными значениями. Матиясевич показал неразрешимость этой проблемы, отобразив диофантово уравнение в рекурсивно перечислимое множество и применив теорему Гёделя о неполноте. [4]
В 1936 году Алан Тьюринг доказал, что проблема остановки — вопрос о том, остановится ли машина Тьюринга на заданной программе — неразрешима во втором смысле этого слова. Этот результат позже был обобщен теоремой Райса .
В 1973 году Сахарон Шела показал , что проблема Уайтхеда в теории групп неразрешима в первом смысле этого слова в стандартной теории множеств. [5]
В 1977 году Пэрис и Харрингтон доказали, что принцип Пэрис-Харрингтона , версия теоремы Рамсея , неразрешим при аксиоматизации арифметики, заданной аксиомами Пеано , но может быть доказана его истинность в более широкой системе арифметики второго порядка .
Теорема Краскала о дереве , которая имеет приложения в информатике, также неразрешима с точки зрения аксиом Пеано, но доказуема в теории множеств. Фактически теорема Краскала о дереве (или ее конечная форма) неразрешима в гораздо более сильной системе, кодифицирующей принципы, приемлемые на основе философии математики, называемой предикативизмом.
Теорема Гудстейна — это утверждение о теории натуральных чисел Рэмси , которая, как показали Кирби и Пэрис, неразрешима в арифметике Пеано.
Грегори Чайтин выдвинул неразрешимые утверждения в алгоритмической теории информации и доказал еще одну теорему о неполноте в этой ситуации. Теорема Чайтина утверждает, что для любой теории, которая может представлять достаточно арифметических действий, существует верхняя граница c такая, что в этой теории нельзя доказать, что ни одно конкретное число не имеет колмогоровскую сложность больше, чем c . В то время как теорема Гёделя связана с парадоксом лжеца , результат Чайтина связан с парадоксом Берри .
В 2007 году исследователи Курц и Саймон, опираясь на более раннюю работу Дж. Х. Конвея в 1970-х годах, доказали, что естественное обобщение проблемы Коллатца неразрешимо. [6]
В 2019 году Бен-Дэвид и его коллеги построили пример модели обучения (названной EMX) и показали семейство функций, обучаемость которых в EMX неразрешима в теории стандартных множеств. [7] [8]
