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