Mengompresi informasi tentang masalah penghentian untuk mesin Turing oracle

Masalah penghentian diketahui tidak dapat diperhitungkan. Namun, dimungkinkan untuk secara "kompres" informasi secara eksponensial tentang masalah penghentian, sehingga pengompresannya dapat dihitung.

Lebih tepatnya, adalah mungkin untuk menghitung dari deskripsi mesin Turing dan saran bit menyatakan jawaban atas masalah penghentian untuk semua dari mesin Turing, dengan asumsi bahwa status saran dapat dipercaya - kami membiarkan penasihat kami memilih bit untuk menggambarkan berapa banyak mesin Turing berhenti dalam biner, tunggu sampai sebanyak itu berhenti, dan hasilkan bahwa sisanya tidak berhenti.$2^{n}-1$2 n - $n$$2^{n}-1$

Argumen ini adalah varian sederhana dari bukti bahwa konstanta Chaitin dapat digunakan untuk menyelesaikan masalah penghentian. Yang mengejutkan saya adalah tajam. Tidak ada peta yang dapat dihitung dari deskripsi mesin Turing dan bit saran menyatakan untuk bit menghentikan output yang mendapatkan jawaban yang tepat, untuk setiap tuple mesin Turing, untuk beberapa tupel bit. Jika ada, kita dapat menghasilkan contoh tandingan dengan mendiagonalisasi, dengan masing-masing dari mesin Turing mensimulasikan apa yang program lakukan pada salah satu dari kemungkinan pengaturan bit dan kemudian memilih negara penghentian sendiri untuk melanggar prediksi. . n 2 n 2 n 2 n$2^n$$n$$2^n$$2^n$$2^n$$n$

Tidak mungkin untuk mengkompres informasi tentang masalah penghentian untuk mesin Turing dengan penghentian sama sekali (tanpa akses ke beberapa jenis peramalan sendiri). Mesin hanya dapat mensimulasikan apa yang Anda prediksi pada semua input yang mungkin, mengabaikan yang mana Anda tidak berhenti, dan memilih waktu berhenti mereka untuk memberikan jawaban leksikografis pertama yang tidak Anda prediksi pada input apa pun.

Ini memotivasi saya untuk berpikir tentang apa yang terjadi pada nubuat lain:

Apakah ada contoh oracle di mana masalah penghentian untuk mesin Turing dengan oracle itu dapat dikompres pada tingkat pertumbuhan menengah antara linier dan eksponensial?

Lebih formal, diberi oracle, misalkan menjadi terbesar sedemikian sehingga ada fungsi parsial yang dapat dihitung dari oracle mesin Turing dan bit ke bit, sehingga untuk setiap -tupel mesin oruring Turing, ada sebuah -tuple bit, di mana nilai fungsi yang dievaluasi pada input itu sama dengan -tuple untuk setiap mesin Turing oracle yang berhenti dan untuk setiap mesin Turing oracle yang berjalan selamanya.m m n m m n m 1 $f(n)$$m$$m$$n$$m$$m$$n$$m$$1$$0$

Apakah ada oracle di mana ? Apakah ada oracle di mana ?ω ( n ) = f ( n ) = o ( 2 n$n<f(n)<2^{n}-1$$\omega(n)=f(n)=o(2^n)$

Biarkan menjadi output dari mesin Turing dilengkapi dengan oracle , pada input . Di sini adalah singkatan dari "jump". (Dalam hal non-stop, tidak terdefinisi.)e A e J J A ( e $J^A(e)$$e$$A$$e$$J$$J^A(e)$

Sebuah oracle adalah melompat-dilacak jika ada komputasi fungsi nondecreasing sehingga untuk semua , untuk beberapa keluarga computably enumerable set terbatas dengan untuk semua .h : N → N e J A ( e ) ∈ T e ( T e ) e ∈ N | T e | ≤ h ( e ) $A$$h:\mathbb N\to\mathbb N$$e$$J^A(e)\in T_e$$(T_e)_{e\in\mathbb N}$$|T_e|\le h(e)$$e$

Mari kita pertimbangkan string panjang menunjukkan pertama dari mesin Turing angka akan dihentikan. (Jika kurang dari berhenti, tidak ditentukan.)n k 0 , ... , n - 1 k f A ( k , n $f^A(k,n)=$$n$$k$$0,\dots,n-1$$k$$f^A(k,n)$

Perhatikan bahwa adalah parsial relatif dihitung untuk . Jadi ada fungsi yang dapat dihitung sedemikian sehingga . A g f A ( k , n ) = J A ( g ( k , n ) $f^A$$A$$g$$f^A(k,n)=J^A(g(k,n))$

Untuk mengompres bit pertama dari hentian yang ditetapkan untuk , cukuplah untuk mengatakan yang mana dari banyak elemen yang benar, di mana dan adalah jumlah yang benar dari menghentikan TM.A h ( e ) T e e = g ( k , n ) $n$$A$$h(e)$$T_e$$e=g(k,n)$$k$

Ada hierarki yang tepat dari oracle yang dapat dilacak (Nies, Computability and Randomness , Theorem 8.5.2). Jadi dengan memilih tepat kecil, kami mendapatkan kandidat untuk oracle seperti yang Anda minta.$h$$A$

Ini adalah kandidat yang cukup baik dalam arti bahwa kita memiliki satu arah (batas atas pada tingkat pertumbuhan) dan bahwa metode yang kita dapatkan dengan batas atas tidak memberikan batas atas yang jauh lebih kecil dari itu.