¿

Considere cualquier lenguaje . Defina s ( L ) ∈ { 0 , 1 } ω (una secuencia infinita de bits) mediante la fórmula recursiva$L$$s(L) \in {\lbrace 0, 1 \rbrace}^\omega$

Aquí es la función característica de L, es decir, χ L ( w ) = 1 para w ∈ L , χ L ( w ) = 0 para w ∉ $\chi_L$$L$$\chi_L(w)=1$$w \in L$$\chi_L(w)=0$$w \notin L$

Un lenguaje se llama un "predictor universal (cerrado)" cuando$U$

Es fácil ver considerando L = U c . Sin embargo, U puede ser recursivo. Para dar un ejemplo, considere el idioma decidido por el algoritmo siguiente A . Dada la entrada w , A ejecuta todos los programas posibles en orden shortlex, permitiendo que cada uno se ejecute por el tiempo t ( | w | ) donde t es una función del crecimiento superpolinomial. Una vez que alcanza un programa R que genera w más uno o más bits y no se detiene, A genera el primer bit $U \notin \mathsf{P}$$L = U^c$$U$$A$$w$$A$$t(|w|)$$t$$R$$w$$A$$R$salida después de . Es fácil ver que (en condiciones suaves en t ) A siempre se detiene y el lenguaje que decide es un predictor universal. A ' s complejidad de tiempo es de aproximadamente 2 n t ( n $w$$t$$A$$A's$$2^nt(n)$

Dado , defina s ( L , a ) por$a \in {\lbrace 0, 1 \rbrace}^\omega$$s(L, a)$

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

Un lenguaje se llama "predictor abierto universal" cuando$V$

1. incluso$\forall w \in V : |w|$
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})$

[Estoy usando índices basados ​​en 0 así que ]$|s_{<2n}| = 2n$

Nuevamente, es fácil ver pero V puede estar en $V \notin \mathsf{P}$$V$$\mathsf{E}$

¿Existe un predictor abierto universal st P V = N P V ?$V$$\mathsf{P}^V=\mathsf{NP}^V$

Estoy especialmente interesado en tener un ejemplo específico de tal o una prueba de que V no existe bajo supuestos razonables como P ≠ N $V$$V$$\mathsf{P} \ne \mathsf{NP}$

La pregunta puede parecer extraña, así que resumiré brevemente mi motivación para ello. Estoy interesado en modelos similares a AIXI de inteligencia artificial. Aquí desempeña el papel del medio ambiente, que supongo que ser eficiente computable, y una desempeña el papel de las acciones del propio agente. Dado una respuesta positiva a la pregunta, es posible construir un agente eficiente computables en relación con V que optimiza una función de utilidad eficiente computable dada u eligiendo sus acciones futuras st U se maximiza asumiendo se comporta el medio ambiente según la predicción de la $L$$a$$V$$u$$u$$V$

No estoy familiarizado con la noción de predictor universal, y no seguí todo lo que escribiste; en particular, no seguí su bosquejo de la prueba de existencia de un predictor universal en E. Pero suponiendo que exista un predictor abierto universal que pertenezca a E, la respuesta a su pregunta es positiva. Y me temo que probablemente te decepcionará la razón.

Editar en la revisión 2: cambié la construcción en respuesta a la restricción agregada en la revisión 2 de la pregunta, pero la idea general es la misma: mezclar un lenguaje difícil en un predictor abierto universal de tal manera que la definición de predictor abierto universal No nota la diferencia.

Deje T = {0 ^{| x |} 11 x : x ∈ {0,1} ^* }. Tenga en cuenta que cada palabra en T tiene una longitud par. Una propiedad importante de T es que no hay palabra en T es un prefijo apropiado de otra palabra en T . Esto implica que si la diferencia simétrica entre dos lenguajes V y W está contenida en T , entonces para cada secuencia infinita s ∈ {0,1} ^ω , hay como máximo una n tal que χ _V ( s _{<2 n} ) ≠ χ_W ( s _{<2 n} ), y en particular V es un predictor abierto universal si y solo si W es un predictor abierto universal.

Es fácil ver que existe un lenguaje EXPSPACE completa que es un subconjunto de T . Deje L ser tal lenguaje. Deje que V sea ​​un predictor abierto universal que pertenece a E y, por lo tanto, también a EXPSPACE. Definir un idioma W = L ∪ ( V ∖ T ). Como V es un predictor abierto universal y la diferencia simétrica entre V y W está contenida en T , W también es un predictor abierto universal. Es fácil ver que W es EXPSPACE-complete, y por lo tanto P ^W = NP ^W= ESPACIO Esto concluye que W satisface la propiedad deseada.