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