Uma pergunta relacionada a uma máquina de Turing com um estado inútil

OK, então aqui está uma pergunta de um teste passado na minha aula de Teoria da Computação:

Um estado inútil em uma TM é aquele que nunca é inserido em nenhuma sequência de entrada. Deixe Prove que \ mathrm {USELESS} _ {\ mathrm {TM}} é indecidível.U S E L E S S T

$$\mathrm{USELESS}_{\mathrm{TM}} = \{\langle M, q \rangle \mid q \text{ is a useless state in }M\}.$$ $\mathrm{USELESS}_{\mathrm{TM}}$

Acho que tenho uma resposta, mas não tenho certeza se está correta. Incluirá na seção de respostas.

Isso é claramente redutível a partir do Problema da Parada. Se uma máquina não parar na entrada , qualquer estado final será "inútil". Dada uma entrada para o problema de , é fácil construir que para em todas as entradas (portanto, seu estado final não é inútil) se e somente se parar em . Dessa forma, você pode decidir o Problema de Parada se puder decidir , o que gera uma contradição.x M , x M x M x U S E L E S S T $M$$x$$M,x$$M_x$$M$$x$$\mathrm{USELESS}_{\mathrm{TM}}$

Para os fins desta prova, assumiremos que é decidível para exibir uma contradição.$\mathrm{USELESS}_{\mathrm{TM}}$

Crie o TM que faça o seguinte:$R$

• Converte o TM em um autômato de empilhamento com uma pilha relaxada (ou seja, sem necessidade de LIFO). Isso é equivalente a um gráfico direcionado detalhando a transição entre os estados deP $M$$P$$M$
• Marque o estado inicial de .$P$
• A partir do estado inicial, inicie uma pesquisa pela primeira vez ao longo de cada borda de saída, marcando cada nó não marcado.
• Quando a pesquisa terminar, se houver algum nó não marcado que corresponda a , aceite ; caso contrário, rejeite .$q$

Em seguida, crie TM = "Na entrada $$$S$

1. Crie o TM como mostrado acima.$R$
2. Execute em .$q$$R$
3. Se retornar aceitar, aceite ; se rejeitar, rejeite " $R$$R$

Portanto, se é um decisor para então é um decisor para (o problema de aceitação). Como é comprovadamente indecidível (consulte o Teorema da Computação da Teoria da Computação 4.11 na página 174), chegamos a uma contradição. Portanto, a hipótese original está incorreta e é indecidível.U S E L E $R$ S A T M A T M L S E L E S S T $\mathrm{USELESS}_{\mathrm{TM}}$$S$$A_{\mathrm{TM}}$$A_{\mathrm{TM}}$$\mathrm{USELESS}_{\mathrm{TM}}$