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

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.

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'$$\Sigma^0_1$$\phi_n$$n$$W_n = \{k \in \mathbb{N} \mid \text{$\phi_n(k)$ is defined}\}$$n$

• $\{n \in \mathbb{N} \mid \text{$\varphi_n$ terminates for finitely many inputs}\}$ está -completo.$\Sigma^0_2$
• $\{n \in \mathbb{N} \mid \text{$\varphi_n$ is a total function}\}$ tem completo.$\Pi^0_2$
• $\{n \in \mathbb{N} \mid \text{$W_n$ is a computable set}\}$ tem .$\Sigma^0_3$

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 $\varphi_n$$n$$n$

[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.