Czy są jakieś istniejące problemy, których nie można rozwiązać za pomocą wyroczni zatrzymującej?

Rozumiem, że większość problemów jest trywialna, jeśli dostępna jest wyrocznia zatrzymująca (lub, moim zdaniem, hiper-obliczenia). Jednak zastosowanie argumentu, który pokazuje, że problem zatrzymania jest niemożliwy dla maszyny Turinga, pokazuje również, że wyrocznia Turinga + nie może zdecydować o problemie zatrzymania dla wyroczni Turinga +. Czy istnieją jakieś rzeczywiste, praktyczne przykłady problemów nierozwiązywalnych przez wyrocznię zatrzymującą?

Uwaga: przez „wyrocznię” rozumiem wyrocznię dla standardowej maszyny Turinga, a nie TM z samą wyrocznią.

Wystarczy wziąć problem, którego stopień Turinga jest większy niż , czyli stopień Wyroczni Stwórczej. Pod względem hierarchii arytmetycznej chcesz problemów, które są powyżej Ď 0 1 . Przykłady takich problemów (gdzie ϕ n jest n-tą funkcją częściowego obliczenia, a W n = { k ∈ N ∣ ϕ n ( k )  jest zdefiniowany } jest n-tym zestawem wyliczalnym obliczalnie):$0'$$\Sigma^0_1$$\phi_n$$n$$W_n = \{k \in \mathbb{N} \mid \text{$\phi_n(k)$ is defined}\}$$n$

• to Σ 0 2 -kompletne.$\{n \in \mathbb{N} \mid \text{$\varphi_n$ terminates for finitely many inputs}\}$$\Sigma^0_2$
• to Π 0 2 -kompletne.$\{n \in \mathbb{N} \mid \text{$\varphi_n$ is a total function}\}$$\Pi^0_2$
• Σ 0 $\{n \in \mathbb{N} \mid \text{$W_n$ is a computable set}\}$ to .$\Sigma^0_3$

Żadnego z nich nie można rozwiązać, nawet jeśli masz Wyrocznię Wyroczni. Rozważmy na przykład drugi przykład: „czy total?” Biorąc pod uwagę jaki sposób Wyrocznia pomagałaby nam zdecydować, czy maszyna Turinga zakodowana przez zatrzymuje się na każdym wejściu? n $\varphi_n$$n$$n$

[Dodano 2014-06-03] Dla „praktycznego” aspektu tego wszystkiego, rozważ problem: programista napisał funkcję void charge_credit_card(int card_number, int amount)i chcielibyśmy wiedzieć, czy funkcja kończy się na wszystkich wejściach. Jest to niemożliwe , aby napisać kompilator, który może automatycznie sprawdzać to w ogóle. Co więcej, nawet jeśli pozwolimy kompilatorowi zadać nam pytania o formie „czy charge_credit_cardkończy się, gdy otrzyma dane wejściowe (k,m)?”, Nadal jest to niemożliwe.