Мне было интересно, в чем разница между рекурсивными и рекурсивно перечислимыми языками с точки зрения остановки и машин Тьюринга. Я знаю, что рекурсивно перечисляемые языки являются подмножеством рекурсивных языков, но я не уверен в отличии от этого.
В чем разница между рекурсивными и рекурсивно перечислимыми языками
comment
Может лучше подойти для cstheory.stackexchange.com или cs.stackexchange .com
- person nawfal schedule 01.11.2015
comment
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что он касается теории вычислений, а не программирования.
- person Raymond Chen schedule 02.11.2015
comment
@RaymondChen Я думаю, что тот факт, что есть теги теории и теории вычислений, оправдывает мой вопрос.
- person Bren schedule 02.11.2015
Ответы (3)
У вас есть связь между R и RE в обратном порядке: R является (правильным) подмножеством RE. По сути, рекурсивный язык — это язык, для которого у вас есть тотальный решающий фактор.
Вспомните определение рекурсивно перечислимых языков как языка, для которого существует частичный решающий модуль; то есть машина Тьюринга, которая, получив на вход слово в вашем алфавите, либо правильно примет/отклонит слово в соответствии с вашим языком, либо, если слово не на вашем языке, может зациклиться навсегда.
Напротив, рекурсивный язык — это язык, для которого существует полный решающий фактор, т. е. язык, который никогда не будет зацикливаться и всегда останавливается либо в состоянии принятия, либо в состоянии отклонения.
Поставив эти два определения рядом друг с другом, становится очевидным, что рекурсивный язык также рекурсивно перечислим, поскольку общий решающий фактор также является частичным (он просто никогда не «выбирает» цикл вместо того, чтобы останавливаться с правильным ответом).
person
Cactus
schedule
02.11.2015
Основное отличие состоит в том, что в рекурсивно-перечислимом языке машина останавливается для входных строк, которые находятся на языке L. Но для входных строк, которые не на языке L, она может останавливаться или не останавливаться.
Когда мы приходим к рекурсивному языку, он всегда останавливается независимо от того, принимается ли он машиной или нет. если он принят, он достигает (q accept) и останавливается. а если не принимается машиной, то до нее напрямую доходят (q останавливаются).
person
Abdulhakim Zeinu
schedule
18.12.2018
Проблема остановки — это канонический пример проблемы RE, но не R
При попытке разделить классы сложности всегда полезно иметь в виду пример, который принадлежит одному, но не другому.
В этом случае каноническим примером является язык, соответствующий проблеме остановки:
HALT = Все пары машины Тьюринга/ввода, которые останавливаются
Хорошо известно, что проблема остановки не может быть детерминистически решена ни одной машиной Тьюринга, и поэтому языка HALT нет в R.
Но HALT явно в RE.
Напомним определение рекурсивно перечислимых языков как:
RE-язык — это язык, в котором существует машина Тьюринга, которая останавливается на каждом члене языка с выходом «да» и, возможно, вечно работает на не-членах.
Итак, мы просто берем машину Тьюринга, которая имитирует другую машину Тьюринга (универсальную машину Тьюринга). Затем эта машина остановится на каждом члене HALT, и поэтому HALT находится в состоянии RE.
Уже один этот факт должен подчеркнуть, насколько сложнее RE, чем R: RE содержит неразрешимые проблемы, для которых невозможно разработать алгоритм для! R, как прямое следствие его определения, этого не делает.
Проблемы, не относящиеся к RE
Также полезно взглянуть на примеры, которые связывают оба:
- https://cs.stackexchange.com/questions/52503/non-recursively-enumerable-languages< /а>
- https://cs.stackexchange.com/questions/12747/relationship-between-undecidable-problems-and-recursively-enumerable-languages
Канонические примеры являются дополнением к HALT: языку всех пар TM/ввод без остановки.
person
Ciro Santilli 新疆再教育营六四事件ۍ
schedule
26.12.2020
