Batas bawah pada jumlah panggilan oracle untuk memecahkan contoh masalah penghentian

Saya menemukan pertanyaan berikut, yang merupakan latihan yang mudah (spoiler di bawah).

Kami diberikan contoh masalah penghentian (yaitu TMs ), dan kami harus memutuskan mana yang benar-benar berhenti di . Artinya, kita perlu menampilkan . Kami diberi oracle untuk masalah penghentian, tetapi kami harus menggunakannya beberapa kali.M 1 , . . . , M n ϵ { i : M saya  berhenti  ϵ $n$$M_1,...,M_n$$\epsilon$$\{i: M_i\text{ halts on }\epsilon\}$

Tidak sulit untuk menunjukkan bahwa itu dapat dilakukan dengan panggilan .$\log (n+1)$

Pertanyaan saya adalah: bisakah kita membuktikan batas bawah? Adakah alasan untuk curiga bahwa ikatan seperti itu akan sangat sulit ditemukan?

Jawaban atas pertanyaan itu sendiri (spoiler, hover mouse):

Pertimbangkan kasus TM. Kita dapat membuat TM yang menjalankan secara paralel, dan berhenti jika setidaknya dua dari mereka berhenti (jika tidak macet). Demikian pula, kita dapat membuat TM yang berhenti jika setidaknya satu dari mereka berhenti. Kami kemudian dapat memanggil oracle pada . Jika berhenti, maka kita dapat menjalankan mesin secara paralel, dan menunggu satu untuk berhenti. Kita kemudian dapat memanggil oracle pada yang terakhir. Jika oracle mengatakan "tidak", maka kami menjalankan oracle pada . Jika berhenti, maka kami menjalankan mesin sampai satu berhenti, dan hanya itu yang berhenti. Jika tidak berhenti, maka tidak ada yang berhenti. Memperluas ini ke mesin itu mudah.H 2 M 1 , M 2 , M 3 H 1 H 2 H 1 H 1$3$$H_2$$M_1,M_2,M_3$$H_1$$H_2$$H_1$$H_1$$n$

Pengamatan pertama tentang pertanyaan ini adalah bahwa tampaknya tidak mungkin untuk diselesaikan dengan menggunakan alat informasi-teoretis, karena kita sangat bergantung pada kemampuan kita untuk mendapatkan informasi dengan menjalankan mesin tanpa nubuat.

Hasilnya dapat ditemukan di

• Beigel, R., Gasarch, WI, Gill, J., dan Owings, J. Terse, superterse, dan set verbose . Memberitahu. dan Komputasi. 103 (1993), no. 1, 68–85.

Bukti mereka sebenarnya menunjukkan bahwa masalah Anda tidak dapat diselesaikan dengan kueri yang kurang dari untuk set apa pun , apalagi untuk masalah penghentian itu sendiri. Untuk beberapa notasi, masalah Anda terkadang dinotasikan dengan atau (tergantung pada notasi favorit Anda untuk masalah penghentian).X C K n C H A L T$\log_2 n$$X$$C_n^K$$C_n^{HALT}$

Untuk ini dan banyak hasil terkait, lihat juga:

• Survei ini oleh Gasarch

• Buku Bounded Queries in Recursion Theory oleh Gasarch dan Martin.

EDIT: Argumen yang saya jawab dengan itu tidak salah, tapi itu agak menyesatkan, dalam hal itu hanya menunjukkan bahwa batas atas harus ketat untuk beberapa (yang sebenarnya sepele, karena harus ketat ketika dan terikat 1).n = $n$$n=2$

Ini argumen yang lebih tepat. Ini menunjukkan bahwa jika batas atas longgar untuk tertentu , maka untuk semua jumlah panggilan oracle yang diperlukan adalah .n n O ( 1 $\log_2 n$$n$ $n$$O(1)$

(Tentunya itu bukan , jadi batas atas tidak pernah longgar! Tapi saya tidak benar-benar membuktikannya di sini, dan memberikan jawaban lain untuk masalah ini, sepertinya tidak layak dikejar.)$O(1)$

Pertimbangkan masalah penghitungan output maksimum :

Diberi -tupel dari mesin Turing, menghitung output maksimum (dari mesin Turing yang berhenti, jika dijalankan pada ). Jika tidak ada yang berhenti, kembalikan 0.( M 1 , ... , M n ) $n$$(M_1,\ldots,M_n)$$\epsilon$

Sebagai fungsi dari , jumlah panggilan oracle kasus terburuk yang diperlukan untuk menghitung fungsi ini sama dengan jumlah yang diperlukan untuk memutuskan mesin mana dari diberikan yang berhenti. (Jika saya tahu mesin mana yang berhenti, saya dapat dengan mudah menghitung output maksimum. Sebaliknya, jika saya ingin tahu mesin mana yang berhenti, mengikuti konstruksi dalam pernyataan masalah, saya dapat membuat mesin di mana berjalan semua mesin yang diberikan secara paralel, maka perhentian dan output jika dari mereka pernah berhenti. Output maksimum akan memberitahu saya nomor yang berhenti. dari yang saya dapat menghitung persis yang berhenti.)n { M ′ i } ( i = 1 , 2 , … , n ) M ′ i n i $n$$n$$\{M'_i\}$ $(i=1,2,\ldots,n)$$M'_i$$n$$i$$i$

Sekarang, misalkan menjadi bilangan bulat terkecil (jika ada) sedemikian rupa sehingga berlaku sebagai berikut:$n_0$$n$

Menggunakan panggilan oracle, seseorang dapat menghitung output maksimum dari mesin yang diberikan. (Yaitu, batas atas tidak ketat untuk .)$C(n) = \max\{k \in \mathbb{Z} : 2^k < n\}$$n$$n$

Jelas , karena . Bahkan, juga, karena , tetapi tidak dapat ditentukan untuk menghitung output maksimum dari mesin yang diberikan (tanpa panggilan oracle). Sekarang pertimbangkan lebih besar :$n_0>1$$C(1) = -1$$n_0>2$$C(2) = 0$$2$$n$

Klaim: Jika terbatas, maka untuk apa pun , seseorang dapat menghitung output maksimum dari mesin yang diberikan dalam panggilan oracle . $n_0$$n$$n$$C(n_0)$(Perhatikan bahwa jika terbatas, maka .)$n_0$$C(n_0) = O(1)$

Bukti. . Kami membuktikannya dengan induksi pada . Kasus-kasus dasar yang , yang dipegang oleh definisi dan .$n$$n\le n_0$$n_0$$C$

Biarkan menjadi TM yang, mengingat mesin Turing apa pun , menghitung output maksimum hanya dengan menggunakan panggilan ke oracle.$Q_0$$n_0$$C(n_0)$

Perbaiki . Diberikan mesin apa pun , hitung output maksimum sebagai berikut.$n>n_0$$n$$M_1,\ldots, M_n$

Fokus pada mesin . Pertimbangkan menjalankan pada mesin ini . Perhatikan bahwa membuat panggilan ke oracle, dan hanya ada kemungkinan tanggapan oleh oracle untuk panggilan ini. Perhatikan bahwa menurut definisi . Biarkan menyatakan th respon mungkin. Untuk setiap , buat sebuah mesin yang mensimulasikan pada mesin-mesin ini sebagai berikut:$M_1,\ldots,M_{n_0}$$Q_0$$n_0$$Q_0$$C(n_0)$$n' = 2^{C(n_0)}$$n' = 2^{C(n_0)} < n_0$$o_i$$i$$i=1,\ldots,n'$$M'_i$$Q_0$

TM (pada input ):$M'_i$$\epsilon$

1. Simulasikan pada mesin , tetapi alih-alih memanggil oracle, anggap oracle merespons sesuai dengan .$Q_0$$n_0$$(M_1,\ldots,M_{n_0})$$o_i$
2. Simulasi ini mungkin tidak berhenti (misalnya jika bukan apa yang akan dikembalikan oleh oracle).$o_i$
3. Jika simulasi berhenti, biarkan menjadi output maksimum yang dikatakan akan diberikan.$h_i$$Q_0$
4. semua mesin . Jika salah satu dari mereka mengeluarkan , berhenti dan keluaran .$n_0$$(M_1,\ldots,M_{n_0})$$h_i$$h_i$

Sekarang, dalam urutan mesin yang diberikan, ganti mesin pertama dengan mesin . Kembalikan nilai yang dihitung dengan mengulangi urutan mesin ini. (Perhatikan bahwa oracle tidak dipanggil sebelum berulang, sehingga oracle hanya dipanggil setelah case dasar tercapai.)$n$$n_0$$M_1,\ldots,M_{n_0}$$n'< n_0$$M'_1,\ldots,M'_{n'}$$n-(n_0-n') < n$

Inilah mengapa perhitungan ini benar. Untuk sedemikian rupa sehingga adalah respons `` benar '' oleh oracle ke kueri, akan berhenti dan memberikan output maksimum yang benar dari mesin asli . Dengan demikian, output maksimum dari mesin setidaknya output maksimum dari mesin . Di sisi lain, pada langkah 4, tidak ada dapat memberikan output yang lebih besar dari output maksimum . Dengan demikian, output maksimum dari mesin$i$$o_i$$Q_0$$M'_i$$n_0$$n'$$(M'_1,\ldots,M'_{n'})$$n_0$$(M_1,\ldots,M_{n_0})$$M'_i$$(M_1,\ldots,M_{n_0})$$n'$$(M'_1,\ldots,M'_{n'})$ sama dengan output maksimum dari mesin yang mereka ganti. QED$n_0$