Каждая неразрешимая проблема, о которой я знаю, попадает в одну из следующих категорий:
Проблемы, которые неразрешимы из-за диагонализации (косвенная самостоятельная ссылка). Эти проблемы, такие как проблема остановки, неразрешимы, потому что вы можете использовать предполагаемое определение языка для построения TM, поведение которого приводит к противоречию. В этот лагерь можно также добавить много неразрешимых проблем, связанных с колмогоровской сложностью.
Проблемы, которые неразрешимы из-за прямой ссылки на себя. Например, универсальный язык может быть показан неразрешимым по следующей причине: если бы он был разрешимым, то можно было бы использовать теорему Клини о рекурсии для построения TM, который получает свою собственную кодировку, спросите, будет ли он принимать свой собственный ввод затем делает обратное.
Проблемы, которые невозможно решить из-за сокращения существующих неразрешимых проблем. Хорошие примеры здесь включают проблему почтовой корреспонденции (сокращение от проблемы остановки) и проблему Entscheidungs.
Когда я преподаю теорию вычислимости своим ученикам, многие ученики тоже это понимают и часто спрашивают меня, есть ли какие-то проблемы, которые мы можем доказать, неразрешимы, в конечном счете, не возвращаясь к какой-то хитрости самоссылки. Я могу доказать неконструктивно, что существует бесконечно много неразрешимых проблем простым аргументом кардинальности, связывающим количество ТМ с количеством языков, но это не дает конкретного примера неразрешимого языка.
Есть ли языки, о которых известно, что они неразрешимы по причинам, которые не перечислены выше? Если да, то, что они и какие методы использовались, чтобы показать их неразрешимость?
источник
Ответы:
Да, такие доказательства есть. Они основаны на теореме о низком базисе .
См. Этот ответ на вопрос : есть ли доказательства неразрешимости проблемы остановки, которая не зависит от самоссылки или диагонализации? вопрос по теории для большего.
источник
id
и»,pg
по ссылке.это не совсем утвердительный ответ, а попытка чего-то близкого к тому, о чем просят, с творческой точки зрения. сейчас в физике существует довольно много проблем, которые «далеки» от математических / теоретических формулировок неразрешимости, и они кажутся все более «отдаленными» и «мало похожими» на исходные формулировки, включающие проблему остановки и т. д .; конечно, они используют проблему остановки в корне, но цепочки рассуждений становятся все более отдаленными и также имеют сильный «прикладной» аспект / характер. к сожалению, в этой области пока что нет никаких хороших исследований. недавняя проблема, которая «на удивление» оказалась неразрешимой в физике, привлекла большое внимание:
В этом вопросе вы, похоже, наблюдаете, что (неформально) все доказательства неразрешимости имеют определенную «самореференциальную» структуру, и это формально доказано в еще более продвинутой математике, так что и проблема остановки Тьюринга, и теорема Годельса могут рассматриваться как примеры одного и того же основного явления. см. например:
Существует также долгая медитация на эту тему (внутренней?) взаимосвязанности самореферентности и неразрешимости в книгах Хофштадтера. другая область, где результаты неразрешимости являются общими и первоначально были несколько «удивительными», связана с фрактальными явлениями. сквозная видимость / значение неразрешимых явлений в природе - это почти общепризнанный физический принцип, впервые замеченный Вольфрамом как «принцип вычислительной эквивалентности» .
источник