Язык, принятый машиной Тьюринга с бесполезным состоянием?

Какой язык принимает машина Тьюринга, состояние которой не входит на вход I?

Конкретно,

  1. Если состояние принятия - это состояние, в которое он никогда не входит, тогда должен ли L={пусто}?

  2. Если состояние отклонения — это состояние, в которое он никогда не входит, тогда должен ли L={все}?

  3. Что, если TM имеет несколько состояний принятия/отклонения?

  4. Что, если состояние, в которое он никогда не входит, не является ни отклонением, ни принятием? Как это повлияет на L?

Я поискал и нашел пару тем, которые помогли доказать, что эта проблема неразрешима, но можно ли ее распознать по Тьюрингу? Со-Тьюринг узнаваем? Оба?


computer-science turing-machines
person yjw    schedule 27.11.2017    source источник
comment
Это, вероятно, лучше адресовать сайту Computer Science.   -  person tadman    schedule 28.11.2017

Ответы (1)


arrow_upward
1
arrow_downward

  1. Если дано, что состояние остановки-принятия никогда не вводится ни для какого входа I, то можно с уверенностью утверждать, что L(M) является пустым множеством. Примечание: неразрешимо и вообще неузнаваемо, так ли это; тем не менее, он является узнаваемым, поскольку вы можете распознать, принимает ли TM что-то.

  2. Если дано, что состояние остановки-отклонения никогда не вводится ни для какого ввода I, то мы не можем утверждать, что L(M) является множеством всех строк. TM может не останавливаться на вводе — никогда не вводить halt-reject или halt-accept — и в этом случае строка не находится в L(M). Примечание: в общем случае неразрешимо и неузнаваемо, когда TM никогда не входит в состояние остановки-отклонения для какого-либо ввода; тем не менее, его можно распознать, поскольку вы можете определить, отвергает ли TM что-то.

  3. Если ПП имеет несколько состояний принятия/отклонения, то мы можем иметь в виду, что известно, что только одно из них никогда не входило или что ни одно из них никогда не входило. Вторая из этих возможностей неотличима от случаев, которые мы рассмотрели в пунктах 1 и 2 выше. Первая из этих возможностей, с другой стороны, неотличима от ТМ с меньшим количеством состояний принятия/отклонения, а то, которое никогда не посещалось, удаляется. Поскольку, вообще говоря, L(M) может быть чем угодно, это означает, что мы ничего не можем сказать о L(M) в данном случае. Примечание: в общем случае неразрешимо и неузнаваемо, не посещает ли TM с несколькими состояниями принятия/отклонения одно из этих состояний на каком-либо входе; тем не менее, его можно распознать, поскольку вы можете распознать, принимает или отклоняет TM что-то, посетив одно или любое из состояний принятия/отклонения.

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

Теперь, возможно, эти вопросы предназначены для конкретного ввода I. В этом случае:

  1. Это просто означает, что I не находится в L(M). Неразрешимо и неузнаваемо решить, принимает ли М I, но оно сопознаваемо в том смысле, что вы можете распознать, принято ли I.

  2. Это ничего не говорит о том, находится ли я в L(M). Неразрешимо и неузнаваемо решить, не отвергает ли M явно I, но оно сопознаваемо в том смысле, что вы можете распознать, отвергается ли I явно.

  3. Если TM никогда не входит в состояние принятия/отклонения на входе I, см. приведенные выше ответы. Если ТМ никогда не входит только в одно состояние принятия/отклонения на входе I, мы ничего не можем сказать о том, находится ли I в L(M). Неразрешимо и вообще неузнаваемо, не заставляю ли я М входить в какое-либо или какое-либо заданное состояние принятия/отклонения, но это со-распознаваемо в том смысле, что вы можете распознать, действительно ли я заставляю ТМ входить в такое состояние.

  4. Это не влияет на L, так как такой НП эквивалентен меньшему НП, в котором удалено непосещенное состояние, и вообще НП может либо принять, либо отклонить любую строку.

person Patrick87    schedule 28.11.2017