Redução de $HALT$ para $A_{TM}$

Question

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/

Answer 1

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.