Para uma máquina de Turing , como é o conjunto de máquinas "menores" que e que aceitam o mesmo idioma?

Pergunto-me como é que que a seguinte linguagem é em . $\mathrm R$

$L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a TM, and } L(M_1)=L(M_2), \text{ and } |\langle M_1\rangle| > | \langle M_2 \rangle| \Bigr\}$

(Eu sei que está em já que existe uma resposta para essa pergunta de múltipla escolha, mas sem explicação). $\mathrm R$

Eu imediatamente pensei que o pois sabemos que verificar se duas máquinas aceitam o mesmo idioma não é realmente decidível, cheguei a pensar: é imediato "False", mas não pode ser porque existem muitas máquinas de Turing que aceitam a mesma resposta e têm códigos diferentes. $L_{M_1} \notin \textrm{co-RE} \cup \textrm{RE}$

Obrigado!

computability undecidability Jozef
fonte

Respostas:

é em , simplesmente porque o número de descrições de máquinas mais pequenas do que um dado Descrição máquina é finita e qualquer língua é finito em . $L_{M_1}$ $R$ $R$

Dave Clarke
fonte

Uma observação importante: embora a linguagem

seja decidível, a função

que realmente encontra a decisão para essa linguagem não é computável. Eu acho que é provavelmente por isso que o resultado é inicialmente contra-intuitivo.

L_{M_{1}}

$L_{M_1}$

f (M) = L_{M}

$f(M) = L_M$

templatetypedef