Está atingindo em menos linhas semi-decidíveis?

Question

Supondo que tenhamos dois programas $ p_1 $ e $ p_2 $ e dois números de linha $ n_1 $ e $ n_2 $ . Faz $ p_1 $ alcance $ n_1 $ em cada etapas computacionais do que $ p_2 $ atinge $ n_2 $ ? Por redução da parada, isso é claramente decidível, mas acho que é semi-decidível.

Para fazer isso, eu construiria um intérprete, que executa $ p_1 $ e $ p_2 $ Simultaneamente passo a passo e conte as etapas para cada programa. Assim que $ p_1 $ atinge $ n_1 $ , comparo o número de etapas para $ n_2 $ e retorne true se for menor. Se $ p_2 $ atinge $ n_2 $ primeiro, eu retorno falso. No caso de nenhum programa atinge $ n_1 $ ou $ n_2 $ , nada acontece (após a semi-decídua).

Answer 1

É apenas semi-decidível se você acessar seu problema de decisão com muito cuidado.E você tem que palavra de tal maneira que o caso em que ambos os programas nunca alcançam sua $ n $ s está na categoria de rejeição.Desde $ \ fraty <\ fraty $ é ambíguo / indefinido eu mencionaria explicitamente este caso em seu problema de decisão.

Outro do que isso, sim, está correto.Sua máquina pára se uma $ p_1 $ ou $ p_2 $ pára (visualização de alcançar $ n $ como apenas outra condição de parada) e fornece a resposta correta em tal cenário.Se você corrigir o problema acima, quando nem $ p_1, p_2 $ pára você está no caso de rejeição e, portanto, você tem permissão para interromper a semi-decidibilidade.