Apakah relatif terhadap prediktor universal?

Pertimbangkan bahasa . Tentukan (urutan bit tak terbatas) dengan rumus rekursifs ( L ) ∈ { 0 , 1 }$L$$s(L) \in {\lbrace 0, 1 \rbrace}^\omega$

Di sini adalah fungsi karakteristik yaitu untuk , untuk L χ L ( w ) = 1 w ∈ L χ L ( w ) = 0 w ∉ $\chi_L$$L$$\chi_L(w)=1$$w \in L$$\chi_L(w)=0$$w \notin L$

Bahasa disebut "prediktor universal (tertutup)" ketika$U$

Mudah untuk melihat dengan mempertimbangkan . Namun, bisa rekursif. Untuk memberikan contoh, pertimbangkan bahasa yang diputuskan oleh algoritma berikut . Diberikan input , menjalankan semua program yang mungkin dalam urutan shortlex, memungkinkan masing-masing untuk mengeksekusi untuk waktu mana adalah fungsi dari pertumbuhan superpolinomial. Setelah mencapai program yang menghasilkan ditambah satu bit atau lebih dan tidak berhenti, menghasilkan bit pertama yang dihasilkan setelah . Mudah untuk melihatnya (dalam kondisi ringan aktif L = U c U A w A t ( | w | ) t R w A R w $U \notin \mathsf{P}$$L = U^c$$U$$A$$w$$A$$t(|w|)$$t$$R$$w$$A$$R$$w$$t$ ) selalu perhentian dan bahasa itu memutuskan adalah prediktor universal. Kompleksitas waktu adalah sekitarA ′ s 2 n t ( n $A$$A's$$2^nt(n)$

Diberi , tentukan oleh s ( L , a $a \in {\lbrace 0, 1 \rbrace}^\omega$$s(L, a)$

s ( L , a ) 2 n + 1 = a

Bahasa disebut "prediktor terbuka universal" ketika$V$

1. $\forall w \in V : |w|$bahkan
2. $\forall L \in \mathsf{P}, a \in {\lbrace 0, 1 \rbrace}^\omega \, \forall n>>0:s(L, a)_{2n}=\chi_V(s(L, a)_{<2n})$

[Saya menggunakan indeks berbasis 0 jadi ]$|s_{<2n}| = 2n$

Sekali lagi mudah untuk melihat tetapi bisa di V $V \notin \mathsf{P}$$V$$\mathsf{E}$

Apakah ada prediktor terbuka universal st ?P V = N P$V$$\mathsf{P}^V=\mathsf{NP}^V$

Saya terutama tertarik untuk memiliki contoh spesifik dari seperti itu atau bukti bahwa tidak ada dengan asumsi yang masuk akal sepertiV P ≠ N $V$$V$$\mathsf{P} \ne \mathsf{NP}$

Pertanyaan itu mungkin tampak aneh, jadi saya akan menjelaskan secara singkat motivasi saya untuk itu. Saya tertarik pada model kecerdasan aritif seperti AIXI. Berikut memainkan peran lingkungan, yang saya asumsikan menjadi efisien dihitung, dan memainkan peran tindakan agen itu sendiri. Mengingat jawaban positif untuk pertanyaan saya, adalah mungkin untuk membangun agen efisien dihitung relatif terhadap yang mengoptimalkan diberikan fungsi utilitas efisien dihitung dengan memilih tindakan masa depan st dimaksimalkan dengan asumsi berperilaku lingkungan sesuai dengan prediksia V u u $L$$a$$V$$u$$u$$V$

Saya tidak terbiasa dengan gagasan prediktor universal, dan saya tidak mengikuti semua yang Anda tulis; khususnya, saya tidak mengikuti sketsa Anda tentang bukti keberadaan prediktor universal di E. Tetapi dengan asumsi bahwa ada prediktor terbuka universal yang dimiliki E, jawaban atas pertanyaan Anda positif. Dan saya khawatir Anda mungkin akan kecewa dengan alasannya.

Sunting dalam revisi 2: Saya mengubah konstruksi sebagai tanggapan atas pembatasan tambahan dalam revisi 2 dari pertanyaan, tetapi gagasan umumnya sama: mencampur bahasa yang keras menjadi prediktor terbuka universal sedemikian rupa sehingga definisi universal open predictor tidak melihat perbedaannya.

Misalkan T = {0 ^{| x |} 11 x : x ∈ {0,1} ^* }. Perhatikan bahwa setiap kata dalam T memiliki panjang genap. Sebuah properti penting dari T adalah bahwa tidak ada kata dalam T adalah awalan yang tepat dari kata lain dalam T . Ini menyiratkan bahwa jika perbedaan simetris antara dua bahasa V dan W terkandung dalam T , maka untuk setiap urutan tak terhingga s ∈ {0,1} ^ω , paling banyak ada satu n sehingga χ _V ( s _{<2 n} ) ≠ χ_W ( s _{<2 n} ), dan khususnya V adalah prediktor terbuka universal jika dan hanya jika W adalah prediktor terbuka universal.

Sangat mudah untuk melihat bahwa ada bahasa EXPSPACE-lengkap yang merupakan bagian dari T . Biarkan L menjadi bahasa seperti itu. Biarkan V menjadi prediktor terbuka universal yang dimiliki E, dan karenanya juga menjadi EXPSPACE. Tentukan bahasa W = L ∪ ( V ∖ T ). Karena V adalah prediktor terbuka universal dan perbedaan simetris antara V dan W terkandung dalam T , W juga merupakan prediktor terbuka universal. Sangat mudah untuk melihat bahwa W adalah EXPSPACE-lengkap, dan karena itu P ^W = NP ^W= EXPSPACE. Ini menyimpulkan bahwa W memenuhi properti yang diinginkan.