Existem problemas existentes que não seriam solucionáveis ​​com um oráculo que parou?

11

Entendo que a maioria dos problemas é trivial se um oráculo de parada estiver disponível (ou, penso, de forma equivalente, hiper-computação). No entanto, aplicar o argumento que mostra o Problema de Halting é impossível para uma máquina de Turing também mostra que é impossível para um oráculo de Turing + decidir o Problema de Halting para um oráculo de Turing +. Existem exemplos reais e práticos de problemas insolúveis por um oráculo que está parando?

Nota: por "oracle" quero dizer oracle para uma máquina de Turing padrão, não para uma TM com um oracle em si.

ike
fonte
2
Não são problemas "arbitrariamente indecidíveis", ver por exemplo, aqui . Não conheço exemplos "práticos" (que também não correspondem ao título que você escolheu); o que qualifica como "prático" para você?
Raphael
Isso não é planejado simplesmente para responder a essa pergunta. Eu reconheci que o problema de parada do próximo nível ainda se aplica.
ike
Além disso, todos os idiomas que não são recursivamente enumeráveis ​​não podem ser reduzidos ao HALT. Exemplos incluem FINITE, vazio, se dois de CFG derivar a mesma língua, etc.

Respostas:

15

Basta pegar um problema cujo grau de Turing esteja acima de , que é o grau do Oracle Halting. Em termos da hierarquia aritmética, você deseja problemas acima de . Exemplos de tais problemas (onde é a ésima função computável parcial e é o - conjunto enumerável computacionalmente):0Σ10ϕnnWn={kNϕn(k) is defined}n

  • {nNφn terminates for finitely many inputs} está -completo.Σ20
  • {nNφn is a total function} tem completo.Π20
  • {nNWn is a computable set} tem .Σ30

Nada disso pode ser resolvido, mesmo se você tiver um Oracle Halting. Por exemplo, considere o segundo exemplo, "is total?" Dado como o Halting Oracle nos ajudaria a decidir se a máquina de Turing codificada por pára em cada entrada? n nφnnn


[Adicionado em 06/06/2014] Para um aspecto "prático" de tudo isso, considere o problema: um programador escreveu uma função void charge_credit_card(int card_number, int amount)e gostaríamos de saber se a função termina em todas as entradas. É impossível escrever um compilador que possa verificar isso automaticamente em geral. Além disso, mesmo se permitirmos que o compilador nos faça perguntas do formulário " charge_credit_cardtermina quando recebida entrada (k,m)?", Ainda é impossível.

Andrej Bauer
fonte
2
Dizendo "Eu não entendo o exemplo" sem explicar o que confunde você não é produtivo. Você leu as páginas relevantes da Wikipedia que eu apontei? Elas estão diretamente relacionadas à sua pergunta; portanto, a primeira coisa que você deve saber é se familiarizar com os conceitos básicos envolvidos.
Andrej Bauer
11
@ike, o exemplo era para ter uma quantidade infinita de int, obviamente. Você realmente precisa que eu escreva BigIntou algo assim, ou então reclamará que a memória do computador é finita?
Andrej Bauer
11
Tanto faz. Eu lhe disse qual era a resposta para sua pergunta. Se você não quiser entendê-lo de boa fé, não nos incomode com perguntas.
18711 Andrej Bauer
2
Um exemplo prático é , o complemento da parada. Isto é Dado um programa arbitrário e uma entrada para o programa, determine se o programa não para. Esse problema, juntamente com qualquer outra linguagem não recursivamente enumerável, não se reduz ao HALT. {<M,w>:M não para em w}HALT¯{<M,w>:M doesn't halt on w}
11
@tAllan: você deve postar isso como resposta. Supera o que o OP considera "prático", mas seu exemplo é certamente melhor que o meu.
Andrej Bauer