Y a-t-il des problèmes existants qui ne pourraient pas être résolus avec un oracle en arrêt?

Je comprends que la plupart des problèmes sont triviaux si un oracle d'arrêt est disponible (ou, je pense de manière équivalente, l'hyper-calcul). Cependant, appliquer l'argument qui montre que le problème d'arrêt est impossible pour une machine Turing montre également qu'il est impossible pour un oracle Turing + de décider du problème d'arrêt pour un oracle Turing +. Existe-t-il des exemples concrets et pratiques de problèmes insolubles par un oracle qui s'arrête?

Remarque: par "oracle", je veux dire oracle pour une machine de Turing standard, pas un TM avec un oracle lui-même.

Prenez juste un problème dont le degré de Turing est supérieur à , qui est le degré de l'Oracle Halting. En termes de hiérarchie arithmétique, vous voulez des problèmes supérieurs à . Exemples de tels problèmes (où est la ème fonction partielle calculable et est le - e ensemble énumérable):$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}\}$ is -complete.$\Sigma^0_2$
• $\{n \in \mathbb{N} \mid \text{$\varphi_n$ is a total function}\}$ est -complete.$\Pi^0_2$
• $\{n \in \mathbb{N} \mid \text{$W_n$ is a computable set}\}$ est -complete.$\Sigma^0_3$

Aucun de ces problèmes ne peut être résolu même si vous avez un Oracle Halting. Par exemple, considérons le deuxième exemple, "is total?" Étant donné comment le Halting Oracle nous aiderait-il à décider si la machine de Turing codée par s'arrête à chaque entrée? n $\varphi_n$$n$$n$

[Ajouté le 03-06-2014] Pour un aspect "pratique" de tout cela, considérons le problème: un programmeur a écrit une fonction void charge_credit_card(int card_number, int amount)et nous aimerions savoir si la fonction se termine sur toutes les entrées. Il est impossible d'écrire un compilateur qui peut vérifier automatiquement cela en général. De plus, même si nous permettons au compilateur de nous poser des questions de la forme "se charge_credit_cardtermine-t-il quand on donne une entrée (k,m)?", C'est toujours impossible.