Apakah ada masalah yang ada yang tidak bisa dipecahkan dengan oracle yang terhenti?

Saya mengerti bahwa sebagian besar masalah sepele jika tersedia oracle yang berhenti (atau, saya pikir setara, hiper-komputasi). Namun, menerapkan argumen yang menunjukkan Masalah Henti tidak mungkin untuk mesin Turing juga menunjukkan bahwa tidak mungkin bagi oracle Turing + untuk memutuskan Masalah Henti untuk oracle Turing +. Apakah ada contoh aktual, praktis, masalah yang tidak dapat dipecahkan oleh oracle yang berhenti?

Catatan: dengan "oracle" Maksud saya oracle untuk mesin Turing standar, bukan TM dengan oracle itu sendiri.

Ambillah masalah yang memiliki gelar Turing di atas , yang merupakan tingkat The Halting Oracle. Dalam hal hierarki aritmatika Anda menginginkan masalah yang ada di atas . Contoh masalah seperti itu (di mana adalah fungsi komputasi parsial ke- dan adalah - set yang dapat dihitung yang dapat dihitung):$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}\}$ adalah .$\Sigma^0_2$
• $\{n \in \mathbb{N} \mid \text{$\varphi_n$ is a total function}\}$ adalah .$\Pi^0_2$
• $\{n \in \mathbb{N} \mid \text{$W_n$ is a computable set}\}$ adalah .$\Sigma^0_3$

Tak satu pun dari ini dapat diselesaikan bahkan jika Anda memiliki Menghentikan Oracle. Sebagai contoh, perhatikan contoh kedua, "is total?" Mengingat bagaimana bantuan terputus-putus Oracle kita memutuskan apakah mesin Turing dikodekan oleh perhentian di setiap masukan?$\varphi_n$$n$$n$

[Ditambahkan 2014-06-03] Untuk aspek "praktis" dari semua ini, pertimbangkan masalahnya: seorang programmer telah menulis suatu fungsi void charge_credit_card(int card_number, int amount)dan kami ingin tahu apakah fungsi tersebut berakhir pada semua input. Tidak mungkin untuk menulis kompiler yang secara otomatis dapat memeriksa ini secara umum. Selain itu, bahkan jika kita mengizinkan kompiler untuk mengajukan pertanyaan kepada kita tentang bentuk "apakah charge_credit_carddiakhiri ketika diberi masukan (k,m)?", Itu masih mustahil.