Parando problema para a máquina fixa de Turing e entrada fixa

Question

Sabe-se que o problema da parada é indecidível mesmo quando corrigimos a máquina de Turing $ m $ ou a entrada $ W $ .

E se fixarmos tanto a máquina e a entrada?Ou seja, é decidível para cada máquina de Turing fixa $ m_0 $ e cada entrada fixa $ w_0 $ que $ m_0 $ parou em $ w_0 $ como entrada?

Answer 1

.

Sabe-se que o problema da parada é indecidível mesmo quando corrigimos a máquina de Turing $ m $ ou a entrada $ W $ .

Você tem que ter mais cuidado com esta declaração. Não é verdade para qualquer máquina de Turing fixa $ m $ que o problema halting $ \ text {halt} _m $ (Decidir sobre a entrada $ W $ Se $ m $ detenha no recipiente de matemática $ W $ ) é indecidível. Por exemplo, se $ m $ é uma máquina que sempre pára, podemos facilmente decidir $ \ text {halt} _m $ Apenas enviando "sim".

O que você provavelmente quis dizer é os seguintes fatos, que são verdadeiros:

.

1. Existe uma máquina de Turing $ m $ tal que o problema $ \ text {halt} _m $ (decidir sobre entrada $ W $ Se $ m $ pára na $ W $ ) é indecidível.

2. para todas as palavras $ W $ , o problema $ { Halt} _W $ (decidindo sobre a entrada $ m $ se $ m $ pára < span class="contêiner matemática"> $ W $ ) é indecidível.

Em particular para o fato 1, podemos receber $ M $ para ser a máquina universal de Turing.

.

E se fixarmos tanto a máquina e a entrada? Ou seja, é decidível para cada máquina de Turing fixa $ m_0 $ e cada entrada fixa $ w_0 $ que < span class="contentor de matemática"> $ m_0 $ parou em $ w_0 $ como entrada?

Sim, o problema se torna trivialmente decidível. Definir a linguagem $ \ text {halt} _ {m_0, w_0} $ para ser o problema de decidir se $ m_0 $ Halts em $ w_0 $ . Mas observe que esse problema não tem mais nenhuma entrada que a resposta depende, como as duas coisas que a resposta podem depender ( $ m_0 $ e $ w_0 $ ) agora estão corrigidos, ou seja, parte da definição de idioma, não parte da entrada. Isso significa que a resposta é apenas "sim" ou "não". Para que possamos decidir trivialmente esse problema usando um programa que sempre diz "sim", ou um programa que sempre diz "não".

Esta é uma armadilha comum sobre a decidibilidade: é útil perguntar se um problema é decidível ou não quando o número de entradas possíveis é infinito. Se houver apenas muitas entradas possíveis, Todos os problemas se tornam decidíveis. Você perguntou se um problema com apenas 1 entrada possível (a entrada vazia) é decidível, e a resposta para isso é sempre sim.