Существуют ли неразрешимые свойства линейных ограниченных автоматов (избегая трюка с пустым языком множеств)? Как насчет детерминированного конечного автомата? (отложить в сторону неразрешимость).
Я хотел бы получить пример (если возможно) неразрешимой проблемы, которая определена без явного использования машин Тьюринга .
Нужна ли полнота по Тьюрингу модели для поддержки неисчислимых задач?
computability
automata
undecidability
Hernan_eche
источник
источник
Ответы:
Неразрешимые проблемы с контекстно-свободными грамматиками, а, следовательно, и с акцепторами pushdown, которые являются ограниченными TM из Википедии ...
Учитывая CFG, генерирует ли он язык всех строк в алфавите терминальных символов, используемых в его правилах?
Учитывая два CFG, они генерируют один и тот же язык?
Учитывая два CFG, может ли первый генерировать все строки, которые может генерировать второй?
Есть много других о CFG / PDA, а также CSG / LBA и многих других моделях "проще, чем TM".
источник
Непонятно, о чем вы спрашиваете в более поздней части вопроса, главным образом потому, что «проблема с моделью машины» не определена.
Позвольте быть быть классом машин и давайте использовать i в качестве кода M i . Мы можем также интерпретировать i как код i- й TM, а затем спросить, что, если M i , остановит i- ю TM? И эта проблема о М я S неразрешима.{ Мя} я Mя я я Mя я Mя
Язык - это просто набор строк, то, какую интерпретацию вы присваиваете строкам, не влияет на разрешимость языка. Если вы не определите формально, что вы подразумеваете под моделью машины, и проблема с этими машинами, ваши последующие вопросы не могут быть даны ответы.
Снова, пункт, который я упомянул выше, применим. Более разумный вопрос: все доказательства неразрешимости проходят через нечто похожее на неразрешимость проблемы остановки для ТМ? (Ответ: есть и другие способы).
Другой возможный вопрос: что является наименьшим подмножеством ТМ, где проблема остановки для них неразрешима. Очевидно, что такой класс должен содержать задачи, которые не останавливаются (в противном случае проблема тривиально разрешима). Мы можем легко создать искусственные подмножества ТМ, где проблема остановки не решаема, не имея возможности вычислить что-нибудь полезное. Более интересный вопрос - о больших разрешимых множествах ТМ, где остановка для них решаема.
Вот еще один момент: как только у вас есть очень маленькая способность манипулировать битами (например, размер полинома ), вы можете создать машину N с тремя входами: e , x и c , так чтобы она выводила 1, если c является прекращение принятия вычисления TM M e на входе x . Тогда вы можете задавать такие проблемы , как: есть с ул N ( е , х , с ) является 1? что является неразрешимой проблемой.C N F N е Икс с с Mе Икс с N( е , х , в )
источник
Существует очень простая неразрешимая проблема для конечных автоматов. Разбейте алфавит на две половины , где буквы в ˉ Σ являются «заштрихованными» копиями. Теперь, учитывая, что конечный автомат A над Σ ∪ ˉ Σ решает, принимает ли он строку, такую, что непробиваемая часть равна запрещенной части (если мы игнорируем столбцы). Например, строка будет в порядке (обе части ).Σ ∪ Σ¯ Σ¯ A Σ ∪ Σ¯ aaa¯a¯б б¯a¯a a a b a
Да, это проблема почтовой корреспонденции, спрятанная в автомате конечных состояний. Полнота Тьюринга далеко не очевидна в этом вопросе. Он находится там, на заднем плане, так как две копии (неразбитые и запрещенные) вместе кодируют очередь, которая сама по себе имеет силу Тьюринга.
источник
Да. Автомат - это непротиворечивая аксиоматическая формулировка теории чисел (например, см. (1) ), и поэтому согласно первой теореме Гёделя о неполноте он должен включать неразрешимые суждения.
Пример:
Любая проблема, которая неразрешима для TM, также неразрешима для любого автомата, который может симулировать TM. Почему? Потому что, если автомат, который является менее мощным, чем ТМ, может выбрать язык, который ТМ не может решить, ТМ должен быть в состоянии решить его, моделируя автомат с получением противоречия.
источник
Эмиль Пост хотел найти ответ именно на этот вопрос: существует ли нерекурсивный (невычислимый) набор, который не решает проблему остановки. Он преуспел лишь частично, но он создал то, что называется простыми наборами .
Из Википедии:
источник