É em relação a um preditor universal?

8

Considere qualquer linguagem . Defina (uma sequência infinita de bits) pela fórmula recursivas ( L ) { 0 , 1 } ωLs(L){0,1}ω

s(L)n=χL(s(L)<n)

Aqui é a função característica de ie para , para L χ L ( w ) = 1 w L χ L ( w ) = 0 w LχLLχL(w)=1wLχL(w)=0wL

Um idioma é chamado de "preditor universal (fechado)" quandoU

LPn>>0:s(L)n=χU(s(L)<n)

É fácil ver considerando . No entanto, pode ser recursivo. Para dar um exemplo, considere a língua decidido pelo seguinte algoritmo . Dada a entrada , executa todos os programas possíveis em ordem curta, permitindo que cada um execute pelo tempo que é uma função do crescimento superpolinomial. Quando ele alcança um programa que gera mais um ou mais bits e não pára, gera o primeiro bit produzido após . É fácil ver que (em condições amenas em L = U c U A w A t ( | w | ) t R w A R w tUPL=UcUAwAt(|w|)tRwARwt ) sempre para e a linguagem que ele decide é um preditor universal. complexidade de tempo de A é de aproximadamenteA ' s 2 n t ( n )AAs2nt(n)

Dado , defina pora{0,1}ωs(L,a)

s ( L , a ) 2 n +

s(L,a)2n=χL(s(L,a)<2n)
s(L,a)2n+1=an

Uma linguagem é chamada de "preditor aberto universal" quandoV

  1. wV:|w|é par
  2. LP,a{0,1}ωn>>0:s(L,a)2n=χV(s(L,a)<2n)

[Eu estou usando índices baseados em 0, então ]|s<2n|=2n

Novamente, é fácil ver mas pode estar em V EVPVE

Existe um preditor aberto universal st ?P V = N P VVPV=NPV

Estou especialmente interessado em ter tanto um exemplo específico de tais ou uma prova, tais não existe sob suposições razoáveis, comoV PN PVVPNP

A pergunta pode parecer estranha, então descreverei brevemente minha motivação para isso. Estou interessado em modelos de inteligência artificial semelhantes ao AIXI. Aqui desempenha o papel do ambiente, que suponho ser computável com eficiência, e desempenha o papel das ações do próprio agente. Dada uma resposta positiva para minha pergunta, é possível construir um agente computável eficientemente em relação a que otimiza uma função utilitária computável eficientemente escolhendo suas ações futuras, se é maximizado assumindo que o ambiente se comporta de acordo com a previsão dea V u u VLaVuuV

Vanessa
fonte
Em termos de ponto de vista da relativização, V = PSPACE funciona.
Tayfun Pay

Respostas:

5

Não estou familiarizado com a noção de preditor universal e não segui tudo o que você escreveu; em particular, não segui seu esboço da prova da existência de um preditor universal em E. Mas, supondo que exista um preditor aberto universal que pertença a E, a resposta à sua pergunta é positiva. E tenho medo de que você provavelmente fique desapontado com o motivo.

Editar na revisão 2: alterei a construção em resposta à restrição adicionada na revisão 2 da pergunta, mas a idéia geral é a mesma: misturar uma linguagem rígida em um preditor aberto universal de tal maneira que a definição de preditor aberto universal não percebe a diferença.

Seja T = {0 | x | 11 x : x 0,1 {0,1} * }. Observe que cada palavra em T tem um comprimento uniforme. Uma propriedade importante da T é que nenhuma palavra em T é um prefixo próprio de outra palavra em T . Isso implica que, se a diferença simétrica entre duas línguas V e W está contida em T , então para cada sequência infinita s ∈ {0,1} ω , existe no máximo um n tal que χ V ( s <2 n ) ≠ χW ( s <2 n ) e, em particular, V é um preditor aberto universal se e somente se W é um preditor aberto universal.

É fácil ver que existe uma linguagem expspace-complete, que é um subconjunto de T . Seja L essa linguagem. Seja V um preditor aberto universal que pertença a E e, portanto, também a EXPSPACE. Defina um idioma W = L ∪ ( VT ). Como V é um preditor aberto universal e a diferença simétrica entre V e W está contida em T , W também é um preditor aberto universal. É fácil ver que W é EXPSPACE completo e, portanto, P W = NP W= EXPSPACE. Isso conclui que W satisfaz a propriedade desejada.

Tsuyoshi Ito
fonte
1
Ha! Bom ponto, mas você me pegou no tecnicismo. Corrigi a definição para afirmar que um preditor aberto universal tem apenas palavras pares. "Preditor universal" é minha própria terminologia. O conceito é inspirado em arxiv.org/abs/cs/0606070, mas Legg evita considerações de complexidade de tempo
Vanessa
1
@ Squark: Hmm, acho que a idéia de mixar em uma linguagem difícil também funciona com a definição revisada e, portanto, acho que isso não é apenas um detalhe técnico, mas preciso pensar mais.
Tsuyoshi Ito 16/02
3
@ Squark: pensei mais. :)
Tsuyoshi Ito
OK, isso não é um detalhe técnico. Valeu!
Vanessa