Não consegue entender as reduções do problema da parada e seu complemento
Quando eu estava passando pelas reduções de$HP$e$\overline{HP}$neste folheto , não entendo como em todos os lugares a seguinte afirmação é feita:$$⟨M,x⟩ \in \overline{HP} ⇒ \text{M does not halt on x} ⇒ M′ \text{ does not accept any strings} ⇒ L(M′)\text{ is finite} ⇒ M′ \in L_5.$$Porque$M$não parando$x$implicar que$M'$não aceita nenhuma string?
Meu entendimento inicialmente era que$M'$é uma máquina de Turing não determinística que executa simultaneamente$M$em todas as entradas possíveis, mas isso não parece certo. Alguém pode dar alguns exemplos,$(L_3, L_4, L_5$se possível) e explique como as reduções são realizadas?
Também não entendo o que$\tau(⟨M,x⟩) = ⟨M'⟩$meios.
Eu entendo como as reduções são feitas depois de ler algumas páginas do Sipser. Eu ainda não entendo como eles são feitos no folheto vinculado. Se alguém puder comentar sobre qual livro usa a mesma notação ou o procedimento de redução que a apostila, seria de muita ajuda!
Respostas
A máquina$M'$ignora sua entrada e apenas simula$M$correndo em$x$. Conseqüentemente:
- Se$M$pára em$x$então$M'$pára em todas as entradas.
- Se$M$não para$x$então$M'$não para em nenhuma entrada.
A notação$\tau(\langle M,x \rangle) = M'$é a definição de uma redução$\tau$a partir de$\overline{HP}$para$L_5$. A entrada para a redução é uma instância do problema da parada, que é um par consistindo de uma máquina de Turing$M$e uma saída$x$, e a saída é a máquina de Turing$M'$descrito acima.