Неразрешимая проблема

В теории вычислимости и теории сложности вычислений — неразрешимая проблема это проблема решения , для которой оказывается невозможным построить алгоритм , который всегда приводит к правильному ответу «да» или «нет». : Примером может служить проблема остановки можно доказать, что не существует алгоритма, который бы правильно определял, останавливается ли в конечном итоге произвольная программа при запуске. ^[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 ) или его отрицание, мы всегда остановимся, и, более того, ответ, который он нам даст, будет истинным (по обоснованности). Это означает, что это дает нам алгоритм для решения проблемы остановки. Поскольку мы знаем, что такого алгоритма не может быть, из этого следует, что предположение о том, что существует непротиворечивая и полная аксиоматизация всех истинных логических утверждений первого порядка о натуральных числах, должно быть ложным.

Примеры неразрешимых проблем

Неразрешимые проблемы могут быть связаны с разными темами, такими как логика , абстрактные машины или топология . Поскольку существует бесчисленное множество неразрешимых задач, ^{[номер 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]

См. также

Примечания

^ Это означает, что существует алгоритм, который в конце концов останавливается, когда ответ « да» , но может работать вечно, если ответ « нет» .
^ Существует бесчисленное множество подмножеств $\{0,1\}^{*}$ , только счетно многие из которых могут быть решены алгоритмами. Однако на любом языке можно сформулировать только счетное число задач решения.

Ссылки

^ «Формальные вычислительные модели и вычислимость» . www.cs.rochester.edu . Проверено 12 июня 2022 г.
^ «проблема решения» . Оксфордский справочник . Проверено 12 июня 2022 г.
^ Ааронсон, Скотт (21 июля 2011 г.). «Теорема Россера через машины Тьюринга» . Shtetl-Оптимизированный . Проверено 2 ноября 2022 г.
^ Матиясевич, Юрий (1970). Диофантовость перечислимых множеств [Enumerable sets are Diophantine]. Doklady Akademii Nauk SSSR (in Russian). 191 : 279–282.
^ Шела, Сахарон (1974). «Бесконечные абелевы группы, проблема Уайтхеда и некоторые конструкции». Израильский математический журнал . 18 (3): 243–256. дои : 10.1007/BF02757281 . МР 0357114 . S2CID 123351674 .
^ Курц, Стюарт А.; Саймон, Янош, «Неразрешимость обобщенной проблемы Коллатца» , в материалах 4-й Международной конференции по теории и приложениям моделей вычислений, TAMC 2007, состоявшейся в Шанхае, Китай, в мае 2007 года. ISBN 3-540-72503-2 . дои : 10.1007/978-3-540-72504-6_49
^ Бен-Давид, Шай; Грубеш, Павел; Моран, Шей; Шпилька, Амир; Иегудаофф, Амир (07.01.2019). «Обучаемость может быть неразрешимой» . Природный машинный интеллект . 1 (1): 44–48. дои : 10.1038/s42256-018-0002-3 . ISSN 2522-5839 . S2CID 257109887 .
^ Рейзин, Лев (2019). «Недоказуемость приходит в машинное обучение» . Природа . 565 (7738): 166–167. Бибкод : 2019Natur.565..166R . дои : 10.1038/d41586-019-00012-4 . ISSN 0028-0836 . ПМИД 30617250 .

[3] Это означает, что существует алгоритм, который в конце концов останавливается, когда ответ « да» , но может работать вечно, если ответ « нет» .

[5] Существует бесчисленное множество подмножеств $\{0,1\}^{*}$ , только счетно многие из которых могут быть решены алгоритмами. Однако на любом языке можно сформулировать только счетное число задач решения.

[1] «Формальные вычислительные модели и вычислимость» . www.cs.rochester.edu . Проверено 12 июня 2022 г.

[2] «проблема решения» . Оксфордский справочник . Проверено 12 июня 2022 г.

[4] Ааронсон, Скотт (21 июля 2011 г.). «Теорема Россера через машины Тьюринга» . Shtetl-Оптимизированный . Проверено 2 ноября 2022 г.

[6] Матиясевич, Юрий (1970). Диофантовость перечислимых множеств [Enumerable sets are Diophantine]. Doklady Akademii Nauk SSSR (in Russian). 191 : 279–282.

[7] Шела, Сахарон (1974). «Бесконечные абелевы группы, проблема Уайтхеда и некоторые конструкции». Израильский математический журнал . 18 (3): 243–256. дои : 10.1007/BF02757281 . МР 0357114 . S2CID 123351674 .

[8] Курц, Стюарт А.; Саймон, Янош, «Неразрешимость обобщенной проблемы Коллатца» , в материалах 4-й Международной конференции по теории и приложениям моделей вычислений, TAMC 2007, состоявшейся в Шанхае, Китай, в мае 2007 года. ISBN 3-540-72503-2 . дои : 10.1007/978-3-540-72504-6_49

[9] Бен-Давид, Шай; Грубеш, Павел; Моран, Шей; Шпилька, Амир; Иегудаофф, Амир (07.01.2019). «Обучаемость может быть неразрешимой» . Природный машинный интеллект . 1 (1): 44–48. дои : 10.1038/s42256-018-0002-3 . ISSN 2522-5839 . S2CID 257109887 .

[10] Рейзин, Лев (2019). «Недоказуемость приходит в машинное обучение» . Природа . 565 (7738): 166–167. Бибкод : 2019Natur.565..166R . дои : 10.1038/d41586-019-00012-4 . ISSN 0028-0836 . ПМИД 30617250 .

[1]

[2]

[номер 1]

[3]

[номер 2]

[4]

[5]

[6]

[7]

[8]