Gibt es irgendwelche Probleme, die mit einem haltenden Orakel nicht lösbar wären?

Ich verstehe, dass die meisten Probleme trivial sind, wenn ein haltendes Orakel verfügbar ist (oder, ich denke gleichwertig, Hyperberechnung). Die Anwendung des Arguments, das das Halteproblem anzeigt, ist für eine Turing-Maschine jedoch unmöglich. Dies zeigt auch, dass es für ein Turing-Orakel unmöglich ist, das Halteproblem für ein Turing-Orakel zu entscheiden. Gibt es tatsächliche, praktische Beispiele für Probleme, die durch ein haltendes Orakel nicht gelöst werden können?

Hinweis: Mit "Orakel" meine ich Orakel für eine Standard-Turing-Maschine, nicht ein TM mit einem Orakel selbst.

Nehmen Sie einfach ein Problem, dessen Turing-Grad über liegt. Dies ist der Grad von The Halting Oracle. In Bezug auf die arithmetische Hierarchie möchten Sie Probleme, die über . Beispiele für solche Probleme (wobei die te teilweise berechenbare Funktion ist und ist das - th rechnerisch aufzählbare Menge):$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}\}$ ist -complete.$\Sigma^0_2$
• ist Π 0 2 -vollständig.$\{n \in \mathbb{N} \mid \text{$\varphi_n$ is a total function}\}$$\Pi^0_2$
• ist Σ 0 3 -vollständig.$\{n \in \mathbb{N} \mid \text{$W_n$ is a computable set}\}$$\Sigma^0_3$

Keines dieser Probleme kann gelöst werden, selbst wenn Sie ein Halting Oracle haben. Betrachten Sie zum Beispiel das zweite Beispiel: " total?" Gegeben n , wie würde die Halting Oracle helfen uns , zu entscheiden , ob die Turing - Maschine von codierten n auf Halte jeden Eingang?$\varphi_n$$n$$n$

[Hinzugefügt am 03.06.2014] Betrachten Sie für einen "praktischen" Aspekt all dies das Problem: Ein Programmierer hat eine Funktion geschrieben void charge_credit_card(int card_number, int amount)und wir möchten wissen, ob die Funktion an allen Eingängen endet. Es ist unmöglich , einen Compiler zu schreiben, der dies im Allgemeinen automatisch überprüfen kann. Selbst wenn wir dem Compiler erlauben, uns Fragen des Formulars " charge_credit_cardBeendet bei Eingabe (k,m)?" Zu stellen, ist dies dennoch unmöglich.