Verificar se a máquina de Turing passa pelo menos k> 2 estados antes de aceitar uma palavra

Question

$ l={\ langle m, k \ rangle \ mid \ existe w \ in l (m) \ texto {tal $ m $ passa pelo menos $ k> 2 $ estados distintos antes de aceitar $ W $}} $

Eu tento pensar em redução para provar que esta linguagem não é nem núcleo. Como se aproximar desse problema?Existe uma dica ou intuição?

Eu costumo verificar se o arroz pode ser usado, mas a pergunta aqui não é sobre a própria linguagem

Answer 1

claramente $ l $ é aceitável (apenas simular $ m $ e acompanhe o número de Estados distintos encontrados durante a simulação). Agora mostramos que não é decidível.

Se $ l $ foram decidíveis, você seria capaz de resolver o problema da parada da seguinte forma: Dado um tm $ t $ e uma entrada $ x \ in \ sigma ^ * $ , construa um TM $ m $ Isso ignora sua entrada, simula $ t $ com entrada $ x $ e, quando a simulação estiver concluída, aceita. Você pode assegurar ainda que, se $ m $ aceita, então também atravessa pelo menos $ 3 $ estados distintos por apenas transição do estado inicial para outro estado (distinto) antes de iniciar a simulação da $ t $ .

Agora verifique se $ \ langle m, 3 \ rangle \ em l $ . Se a resposta for afirmativa, então há alguma $ w \ in \ sigma ^ * $ para os quais $ m (W) $ aceita, mostrando que $ t (x) $ pára. Se a resposta for negativa, então $ m $ nunca pára, mostrando que $ t (x) $ não halt.