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

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален Найдите источники: «Неразрешимая проблема»  – Новости  · газеты  · книги  · ученый  · JSTOR (Июль 2019) (Узнайте, как и когда удалить этот шаблон сообщения)

В теория вычислимости и теория сложности вычислений, неразрешимая проблема это проблема решения для которого оказалось невозможным построить алгоритм это всегда приводит к правильному ответу «да» или «нет». В проблема остановки это пример: можно доказать, что не существует алгоритма, который правильно определяет, останавливаются ли произвольные программы при запуске.

Фон

Проблема решения - это любой произвольный вопрос типа «да» или «нет» для бесконечного набора входных данных. Из-за этого традиционно проблема решения определяется эквивалентно как набор входных данных, для которых проблема возвращается. да. Эти входные данные могут быть натуральными числами, а также другими значениями другого типа, например струны из формальный язык. Используя некоторую кодировку, такую ​​как Гёделевская нумерация, строки могут быть закодированы как натуральные числа. Таким образом, проблема принятия решения, неформально сформулированная в терминах формального языка, также эквивалентна набору натуральные числа. Для упрощения формального определения оно сформулировано в терминах подмножеств натуральных чисел.

Формально проблема решения - это подмножество натуральных чисел. Соответствующая неформальная проблема состоит в том, чтобы решить, входит ли данное число в набор. Проблема решения А называется разрешимым или эффективно разрешимым, если А это рекурсивный набор и неразрешимым в противном случае. Проблема называется частично разрешимой, полуразрешимой, разрешимой или доказуемой, если А это рекурсивно перечислимый набор^[1].

Пример: проблема остановки в теории вычислимости

В теория вычислимости, то проблема остановки это проблема решения который можно сформулировать следующим образом:

Учитывая описание произвольной программа и конечный ввод, решите, завершит ли программа выполнение или будет работать вечно.

Алан Тьюринг в 1936 г. доказал, что генерал алгоритм работает на Машина Тьюринга это решает проблему остановки для все возможные пары программа-ввод не могут существовать. Следовательно, проблема остановки заключается в неразрешимый для машин Тьюринга.

Связь с теоремой Гёделя о неполноте

Концепции, поднятые Теоремы Гёделя о неполноте очень похожи на те, которые возникают в связи с проблемой остановки, и доказательства очень похожи. Фактически, более слабая форма Первой теоремы о неполноте является простым следствием неразрешимости проблемы остановки. Эта более слабая форма отличается от стандартной формулировки теоремы о неполноте тем, что утверждает, что аксиоматизация натуральных чисел, которое является как полным, так и звук невозможно. «Здоровая» часть - это ослабление: это означает, что мы требуем, чтобы рассматриваемая аксиоматическая система доказывала только истинный утверждения о натуральных числах. Поскольку разумность подразумевает последовательность, эту более слабую форму можно рассматривать как следствие сильной формы. Важно отметить, что утверждение стандартной формы первой теоремы Гёделя о неполноте совершенно не связано с истинностью утверждения, а касается только вопроса о том, можно ли найти его с помощью математическое доказательство.

Более слабая форма теоремы может быть доказана из неразрешимости проблемы остановки следующим образом. Предположим, что у нас есть звук (и, следовательно, непротиворечивый) и полный аксиоматизация всего правда логика первого порядка заявления о натуральные числа. Затем мы можем построить алгоритм, который перечислит все эти утверждения. Значит, есть алгоритм N(п), что при натуральном числе п, вычисляет истинное логическое утверждение первого порядка о натуральных числах, и что для всех истинных утверждений существует хотя бы один п такой, что N(п) приводит к этому утверждению. Теперь предположим, что мы хотим решить, будет ли алгоритм с представлением а останавливается при вводе я. Мы знаем, что это утверждение может быть выражено логическим утверждением первого порядка, например ЧАС(а, я). Из полной аксиоматизации следует, что либо существует п такой, что N(п) = ЧАС(а, я) или есть п ' такой, что N(п ') = ¬ ЧАС(а, я). Итак, если мы повторять общий п пока мы не найдем ЧАС(а, я) или его отрицание, мы всегда будем останавливаться, и, более того, ответ, который он нам дает, будет истинным (по разумности). Это означает, что это дает нам алгоритм для решения проблемы остановки. Поскольку мы знаем, что такого алгоритма быть не может, отсюда следует, что предположение о том, что существует непротиворечивая и полная аксиоматизация всех истинных логических утверждений первого порядка о натуральных числах, должно быть ложным.

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

Неразрешимые проблемы могут быть связаны с разными темами, такими как логика, абстрактные машины или же топология. Поскольку есть бесчисленно много неразрешимых проблем,^[2] любой список, даже один из бесконечная длина, обязательно неполный.

Примеры неразрешимых утверждений

В современном употреблении слово «неразрешимый» имеет два различных значения. Первый из них - это смысл, используемый по отношению к теоремам Гёделя: утверждение, которое нельзя ни доказать, ни опровергнуть в указанном дедуктивная система. Второй смысл употребляется по отношению к теория вычислимости и относится не к заявлениям, а к проблемы решения, которые представляют собой счетное бесконечное множество вопросов, каждый из которых требует ответа «да» или «нет». Такая проблема называется неразрешимой, если нет вычислимая функция который правильно отвечает на все вопросы из набора задач. Связь между этими двумя понятиями заключается в том, что если проблема принятия решения неразрешима (в теоретическом смысле рекурсии), то не существует последовательной, эффективной формальная система что доказывает на каждый вопрос А в задаче либо "ответ на А да "или" ответ на А нет".

Из-за двух значений слова неразрешимый термин независимый иногда используется вместо неразрешимого в смысле «ни доказать, ни опровергнуть». Однако использование слова «независимый» также неоднозначно. Это может означать просто «недоказуемо», оставляя открытым вопрос о том, можно ли опровергнуть независимое утверждение.

Неразрешимость утверждения в конкретной дедуктивной системе сама по себе не решает вопроса о том, значение истины утверждения четко определено, или его можно определить другими способами. Неразрешимость подразумевает лишь то, что рассматриваемая конкретная дедуктивная система не доказывает истинность или ложность утверждения. Существуют ли так называемые «абсолютно неразрешимые» утверждения, значение истинности которых никогда не может быть известно или плохо определено, является спорным вопросом среди различных философские школы.

Одной из первых проблем, которую считали неразрешимой во втором смысле этого слова, была проблема проблема слов для групп, впервые поставленный Макс Ден в 1911 году, который спрашивает, существует ли конечно представленная группа для которых не существует алгоритма определения эквивалентности двух слов. Это было показано в 1952 году.

Совместная работа Гёделя и Пол Коэн привел два конкретных примера неразрешимых утверждений (в первом смысле этого слова): гипотеза континуума нельзя ни доказать, ни опровергнуть в ZFC (стандартная аксиоматизация теория множеств ), а аксиома выбора нельзя ни доказать, ни опровергнуть в ZF (это все аксиомы ZFC Кроме аксиома выбора). Эти результаты не требуют теоремы о неполноте. В 1940 году Гёдель доказал, что ни одно из этих утверждений не может быть опровергнуто в теории множеств ZF или ZFC. В 1960-х Коэн доказал, что ни то, ни другое нельзя доказать с помощью ZF, а гипотеза континуума не может быть доказана с помощью ZFC.

В 1970 году русский математик Юрий Матиясевич показало, что Десятая проблема Гильберта, поставленная в 1900 году как вызов математикам следующего века, не может быть решена. Задача Гильберта заключалась в поиске алгоритма, который находит все решения Диофантово уравнение. Диофантово уравнение является более общим случаем Последняя теорема Ферма; мы ищем целые корни из многочлен в любом количестве переменных с целыми коэффициентами. Поскольку у нас есть только одно уравнение, но п переменных существует (и их легко найти) бесконечно много решений в комплексная плоскость; однако проблема становится невозможной, если решения ограничиваются только целыми значениями. Матиясевич показал неразрешимость этой проблемы, отображая диофантово уравнение в рекурсивно перечислимый набор и используя теорему Гёделя о неполноте.^[3]

В 1936 г. Алан Тьюринг доказал, что проблема остановки - вопрос о том, является ли Машина Тьюринга останавливается на данной программе - неразрешимо во втором смысле этого слова. Позднее этот результат был обобщен Теорема Райса.

В 1973 г. Сахарон Шелах показал Проблема Уайтхеда в теория групп неразрешима в первом смысле этого слова в стандартной теории множеств.

В 1977 году Пэрис и Харрингтон доказали, что Принцип Пэрис-Харрингтона, версия Теорема Рамсея, неразрешима в аксиоматизации арифметики, данной аксиомами Пеано, но может быть доказана в более широкой системе арифметика второго порядка.

Теорема Крускала о дереве, который имеет приложения в информатике, также неразрешим с помощью аксиом Пеано, но доказуем в теории множеств. Фактически теорема Крускала о дереве (или ее конечная форма) неразрешима в гораздо более сильной системе, кодифицирующей принципы, приемлемые на основе философии математики, называемой предикативизмом.

Теорема Гудштейна это заявление о Теория Рамсея натуральных чисел, которые показали Кирби и Пэрис, неразрешима в арифметике Пеано.

Григорий Чайтин произвел неразрешимые заявления в алгоритмическая теория информации и доказал еще одну теорему о неполноте в этом случае. Теорема Чейтина утверждает, что для любой теории, которая может представить достаточно арифметических операций, существует верхняя граница c так что никакое конкретное число не может быть доказано в этой теории, чтобы иметь Колмогоровская сложность лучше чем c. Хотя теорема Гёделя связана с парадокс лжеца, Результат Чайтина связан с Парадокс Берри.

В 2007 году исследователи Курц и Саймон, опираясь на более раннюю работу J.H. Конвей в 1970-х годах доказал, что естественное обобщение Проблема коллатца неразрешима.^[4]

Смотрите также

• Разрешимость (логика)
• Entscheidungsproblem
• Доказательство невозможности
• Злая проблема

Рекомендации

1. ^ Это означает, что существует алгоритм, который в конечном итоге останавливается, когда ответ да но может бежать вечно, если ответ нет.
2. ^ Существует несчетное количество подмножеств ${ Displaystyle {0,1 } ^ {*}}$, только счетное множество из которых можно решить с помощью алгоритмов. Тем не менее, на любом языке можно сформулировать лишь счетное число задач, связанных с решением.
3. ^ Матиясевич Юрий (1970). Диофантовость перечислимых множеств [Перечислимые множества диофантовы]. Доклады Академии Наук СССР (на русском). 191: 279–282.
4. ^ Курц, Стюарт А .; Симон, Янош, «Неразрешимость обобщенной проблемы Коллатца», в материалах 4-й Международной конференции по теории и приложениям моделей вычислений, TAMC 2007, проходившей в Шанхае, Китай, в мае 2007 г. ISBN  3-540-72503-2. Дои:10.1007/978-3-540-72504-6_49