Существуют ли какие-либо конкретные проблемы, о которых известно, что они неразрешимы по причинам, отличным от диагонализации, самоссылки или сводимости?

28

Каждая неразрешимая проблема, о которой я знаю, попадает в одну из следующих категорий:

  1. Проблемы, которые неразрешимы из-за диагонализации (косвенная самостоятельная ссылка). Эти проблемы, такие как проблема остановки, неразрешимы, потому что вы можете использовать предполагаемое определение языка для построения TM, поведение которого приводит к противоречию. В этот лагерь можно также добавить много неразрешимых проблем, связанных с колмогоровской сложностью.

  2. Проблемы, которые неразрешимы из-за прямой ссылки на себя. Например, универсальный язык может быть показан неразрешимым по следующей причине: если бы он был разрешимым, то можно было бы использовать теорему Клини о рекурсии для построения TM, который получает свою собственную кодировку, спросите, будет ли он принимать свой собственный ввод затем делает обратное.

  3. Проблемы, которые невозможно решить из-за сокращения существующих неразрешимых проблем. Хорошие примеры здесь включают проблему почтовой корреспонденции (сокращение от проблемы остановки) и проблему Entscheidungs.

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

Есть ли языки, о которых известно, что они неразрешимы по причинам, которые не перечислены выше? Если да, то, что они и какие методы использовались, чтобы показать их неразрешимость?

templatetypedef
источник
@ EvilJS Насколько я понимаю, доказательство неразрешимости было связано с умением моделировать ТМ, хотя, возможно, я ошибаюсь?
templatetypedef
Можно сказать, что теорема Райса может не вписаться ни в одну из этих категорий, но доказательство теоремы подходит.
Райан
1
@EvilJS Это хороший момент. На самом деле, то, что я ищу здесь, это то, есть ли какая-то принципиально другая техника, которую мы можем использовать. Было бы хорошо, например, если бы кто-то идентифицировал проблему как неразрешимую в случае, когда эта проблема не имеет известной связи с самоссылкой ТМ или аргументом типа Годелинга. Если лучшее, что мы можем сделать, это «мы выяснили это давным-давно, то поняли, что это проще доказать другим способом», что в некотором смысле было бы ответом - три метода, приведенные выше, в основном объясняют все доказательства неразрешимость, о которой мы знаем.
templatetypedef
2
Функция занятого бобра растет слишком быстро для любой программы, чтобы вычислить. Конкретно, вы можете определить функцию как единицу плюс наибольшее число, вычисляемое программой длиной не более n . Это считается диагонализацией? е(N)N
Юваль Фильмус
1
@YuvalFilmus Возможно, я здесь слишком строг, но для меня это звучит как аргумент диагонального типа: вы создаете функцию, которая определена так, чтобы отличаться от всех функций, вычисляемых ТМ.
templatetypedef

Ответы:

10

Да, такие доказательства есть. Они основаны на теореме о низком базисе .

См. Этот ответ на вопрос : есть ли доказательства неразрешимости проблемы остановки, которая не зависит от самоссылки или диагонализации? вопрос по теории для большего.

Кава
источник
Если кто-то интересуется передовыми методами в теории вычислимости, посмотрите книги Роберта И. Соаре « Рекурсивно перечислимые множества и степени и теория вычислимости и приложения» .
Каве
Поправьте меня, если я ошибаюсь, но разве доказательство теоремы о низком базисе не включает в себя применение функционала к себе и вопрос, не производит ли он значение? Если так, разве это не просто слой косвенности поверх диагонального аргумента?
templatetypedef
@templatetypedef, я не эксперт, но, насколько я понимаю, нет. Смотрите, например, страницу 109 в книге Соаре.
Каве
@templatetypedef, ps1: в вопросе о том, что мы считаем диагонализацией, есть некоторая неопределенность. Если мы не будем осторожны, мы можем расширять то, что мы считаем диагонализацией, каждый раз, когда мы видим что-то, чего не было. Возьмите, например, методы приоритета или любой общий метод построения объектов по частям таким образом, чтобы избежать равенства с любым объектом из данного класса.
Каве
2
@David, :) Я открываю страницу из книги, которой хочу поделиться, нажимаю кнопку «Поделиться» сверху и удаляю параметры, кроме « idи», pgпо ссылке.
Каве
0

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

Спектральная щель - разность энергий между основным состоянием и первым возбужденным состоянием системы - является центральной в квантовой физике многих тел. Многие сложные открытые проблемы, такие как гипотеза Холдейна, вопрос о существовании расщепленных топологических спиновых жидких фаз и гипотеза Янга – Миллса, касаются спектральных промежутков. Эти и другие проблемы являются частными случаями общей проблемы спектральной щели: с учетом гамильтониана квантовой системы многих тел она является зазором или щелью? Здесь мы докажем, что это неразрешимая проблема. В частности, мы строим семейства квантовых спиновых систем на двумерной решетке с трансляционно-инвариантными взаимодействиями ближайших соседей, для которых проблема спектральной щели неразрешима. Этот результат распространяется на неразрешимость других низкоэнергетических свойств,

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

Теорема об остановке, теорема Кантора (неизоморфизм множества и его набор степеней) и теорема Гёделя о неполноте - все это примеры теоремы Лаврэра о неподвижной точке, которая говорит, что для любой декартовой замкнутой категории, если существует эпиморфное отображение e: A → (A⇒B), то каждое f: B → B имеет неподвижную точку.

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

ВЗН
источник
другие «неожиданные / прикладные» области неразрешимости: апериодические наклоны , возможная стабилизация в конуэйской игре Life ( клеточные автоматы )
vzn
3
Насколько я понимаю, доказательства того, что все эти проблемы неразрешимы, сводятся к сокращению проблемы остановки. Это неправильно?
templatetypedef
ответ в основном допускает, что (все известные результаты неразрешимости могут быть сведены к проблеме остановки). Ваш вопрос почти сформулирован как гипотеза, и я не знаю каких-либо противоречивых знаний о нем, и вижу множество косвенных доказательств в его пользу. но наиболее близким к формальному известному доказательству, по-видимому, являются формулировки неразрешимости с фиксированной точкой (кажется, что нет других формальных формулировок «самоссылки»). Другой способ сказать все это состоит в том, что полнота по Тьюрингу и неразрешимость являются двумя взглядами. по сути того же явления.
взн