É $ nhalt $ indecidível mesmo se $ m $ pára na entrada $ w $ em etapas finitas

Question

Se tivermos a linguagem

$ nhalt= {; $ $ m $ páraentrada $ W $ em menos de $ n $ etapas $\} $

Esta linguagem também é indecida da mesma maneira que $ halt $ é indecidável?E se sim, $ nhalt \ notin p $ , certo?

Answer 1

Esta linguagem é obviamente decidível, basta emular $ m $ em $ W $ e veja se eleparado dentro de $ n $ etapas ou não ...

Agora, para se $ NHALT \ em P $ ou $ NHALT \ Notin P $ .O comprimento da $ n $ aqui é logarítmico ao seu "valor" (assumindo que $ \ sigma $ aquinão é unário).Assim, o número de etapas que precisaremos emular seria exponencial em seu tamanho!Eu não vejo um algoritmo de tempo polinômio para isso, então eu suponho que provavelmente não está em p .Mas eu não provou que (apenas deu intuição sobre por que poderia ser o caso), e há também uma chance de mostrar que é equivalente a algum problema aberto (talvez de alguma forma que você pudesse provar sua $ \ mathcal {np-completo} $ ?)