Considere qualquer linguagem . Defina (uma sequência infinita de bits) pela fórmula recursivas ( L ) ∈ { 0 , 1 } ω
Aqui é a função característica de ie para , para L χ L ( w ) = 1 w ∈ L χ L ( w ) = 0 w ∉ L
Um idioma é chamado de "preditor universal (fechado)" quando
É 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 t ) sempre para e a linguagem que ele decide é um preditor universal. complexidade de tempo de A é de aproximadamenteA ' s 2 n t ( n )
Dado , defina por
s ( L , a ) 2 n +
Uma linguagem é chamada de "preditor aberto universal" quando
- é par
[Eu estou usando índices baseados em 0, então ]
Novamente, é fácil ver mas pode estar em V E
Existe um preditor aberto universal st ?P V = N P V
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 P ≠ N P
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 V
Respostas:
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 ∪ ( V ∖ T ). 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.
fonte