Redução de $HALT$ para $A_{TM}$
-
29-09-2020 - |
Pergunta
Eu conheço a redução para de $A_{TM}$ para $PARAR$.Mas é a seguinte redução de $PARAR$ para $A_{TM}$ correto?
Estamos procurando uma função computável total $f$ mapeamento de $PARAR$ para $A_{TM}$.A seguinte TM $F$ calcula a redução $f$.
F = on input <T, w>
create the following TM T':
T' = on input v:
start T on v
if T accepts or rejects, *accept*
return <T',w>
Eu acho que a linha if T accepts or rejects, *accept*
está correto, mas seria ótimo se alguém pudesse verificar isso.
Editar:Encontrei os seguintes slides, mas não acho que a construção neles esteja correta: http://slideplayer.com/slide/13791105/
Solução
Existem várias noções de "redução". Você descreveu corretamente um redução de muitos-um de $PARAR$ para $A_{TM}$.A redução à qual você vinculou (link mais específico aqui) é em vez disso um redução da tabela verdade.Estes são objetos mais gerais (portanto, seu resultado é mais forte).Cada um, por sua vez, é incluído na noção muito mais ampla de Redução de Turing.
Embora as reduções muitos-um sejam geralmente a noção padrão na teoria da complexidade, as reduções de Turing e as reduções resultantes estrutura de graduação são o padrão na teoria da computabilidade.Observe que se tudo o que quero fazer é provar a indecidibilidade de algum conjunto, uma redução de Turing de algum conjunto conhecido como indecidível é suficiente.
Primeiro, vamos relembrar explicitamente as definições das linguagens envolvidas:
$A_{TM}=\{\langle M,w angle:milhões de dólares para e aceita na entrada $w\}$.
$HALT=\{\langle M,w angle:milhões de dólares pára na entrada $w\}$.
A sua proposta de redução de $PARAR$ para $A_{TM}$ é correto:dado $M$, podemos construir de forma computacional uma nova máquina $\hat{M}$ que aceita precisamente aquelas strings nas quais $M$ pára.(Basicamente, basta substituir todos os estados "rejeitados" em $M$ por estados de "aceitar".)
Agora vamos dar uma olhada na outra redução à qual você vinculou (link mais específico aqui).
Basicamente, em vez de "todos os estados hesitantes aceitam", o argumento vinculado considera separadamente:
a máquina original e
a máquina “contrária” que aceita exatamente quando a original rejeita e vice-versa.
Uma resposta afirmativa para qualquer um dos casos em $A_{TM}$ garante uma resposta afirmativa para a máquina original em $PARAR$.
Pensando bem, não vejo razão para fazer isso em vez de seguir seu argumento, especialmente porque produz um resultado mais fraco, mas é correto e é suficiente para provar a afirmação mais ampla nos slides, ou seja, que $A_{TM}$ é indecidível.