Для машины Тьюринга , как можно определить множество машин которые «короче», чем и которые принимают тот же язык?

14

Интересно, почему следующий язык находится в ?R

LM1={M2|M2 is a TM, and L(M1)=L(M2), and |M1|>|M2|}

(Я знаю, что это в так как есть ответ на этот вопрос с несколькими вариантами ответов, но без объяснения).R

Я сразу подумал, что поскольку мы знаем, что проверка того, что две машины принимают один и тот же язык, на самом деле не решаема, я : действительно ли это немедленно? «Ложь», но этого не может быть, так как есть много машин Тьюринга, которые принимают один и тот же ответ и имеют разные кодировки.LM1co-RERE

Благодарность!

Юзеф
источник

Ответы:

14

в R просто потомучто количество описаний машин меньше заданное машинное описание конечно и любой конечный язык в R .LM1RR

Дэйв Кларк
источник
9
Важное примечание: хотя язык разрешим, функция f ( M ) = L M, которая фактически находит решающее значение для этого языка, не вычислима. Я думаю, что это, вероятно, почему результат изначально нелогичным. LM1f(M)=LM
templatetypedef