<p>Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula</p>

<p>$$s(L)_n=\chi_L(s(L)_{&lt;n})$$</p>

<p>Here $\chi_L$ is the characteristic function of $L$ i.e. $\chi_L(w)=1$ for $w \in L$, $\chi_L(w)=0$ for $w \notin L$</p>

<p>A language $U$ is called a "universal predictor" when</p>

<p>$$\forall L \in \mathsf{R} \, \forall n&gt;&gt;0:s(L)_n=\chi_U(s(L)_{&lt;n})$$</p>

<p>A famous example is <a href="http://www.vetta.org/documents/disSol.pdf" rel="nofollow">Solomonoff induction</a></p>

<p>It is easy to see $U \notin \mathsf{R}$ by considering $L = U^c$. The question is</p>

<blockquote>
  <p>Is there a universal predictor $U \in \mathsf{P/poly}$?</p>
</blockquote>

<p>More specifically</p>

<blockquote>
  <p>Is Solomonoff induction in $\mathsf{P/poly}$?</p>
</blockquote>

<p>It is not hard to see that a positive answer would imply $\exists A \in \mathsf{TALLY}:\mathsf{R} \subset \mathsf{E}^A$ ($A$ is s.t. $U$ is Cook-reducible to $A$ and we have $\mathsf{R} \subset \mathsf{E}^A$ since it is possible to apply $U$ to the sequence $\chi_L(n)$ to decide $L$ in exponential time). This implication seems surprising but I don't see why it's necessarily false</p>

<p>EDIT: Actually such $A$ exists: </p>

<p>$\lbrace w | \exists i,j \in \mathbb{N} : i \in L_j$ and $|w| = f(i,j) \rbrace$</p>

<p>Here $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ is a bijection computable in polynomial time and $L_j$ is the $j$-th recursive language (I'm using an arbitrary enumeration of the recursive languages)</p>

<p>However a universal predictor in $\mathsf{P/poly}$ implies a stronger statement, namely, that there is $A \in \mathsf{TALLY}$ and some fixed polynomial $p(n)$ such that all languages in $\mathsf{TALLY} \cap \mathsf{R}$ can be computed in time $p(n)$ given an oracle for $A$</p>

<p>EDIT: The answer to the first question is positive. Showing this is equivalent to constructing a Turing machine with a special tape on which some fixed (input-independent) infinite string is written in the initial state s.t. this machine computes a universal predictor in polynomial time. To do this, imagine the special tape to be 2-dimensional. In row $i$ of the tape write infinite computable sequence number $i$ (i.e. computed by program $i$). The predictor then works as follows. Given an input of length $n$ it compares it to the first $n$ infinite computable sequences. The first sequence which matches the input is used for the prediction. If no sequence yields a match the predictor outputs $0$.</p>

CC BY-SA 3.0
2013-02-27T09:36:05.023Z
What is $\mathsf{R}$ ?
Jan Johannsen
CC BY-SA 3.0
2013-02-27T09:48:02.080Z
The class of recursive languages, I guess.
MassimoLauria
CC BY-SA 3.0
2013-02-28T20:33:20.360Z
@JanJohannsen Yes, it is the class of recursive languages
Vanessa
CC BY-SA 3.0
2013-03-01T00:29:08.830Z
The answer to the first question is positive, I'll explain why later
Vanessa
<cc.complexity-theory><advice-and-nonuniformity>
Is Solomonoff Induction in $\mathsf{P/poly}$?
Vanessa
# Is Solomonoff Induction in $\mathsf{P/poly}$?

(Asked by: username_0 on 2013-02-26)

Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula

$$s(L)\_n=\chi\_L(s(L)\_{

Here $\chi\_L$ is the characteristic function of $L$ i.e. $\chi\_L(w)=1$ for $w \in L$, $\chi\_L(w)=0$ for $w \notin L$

A language $U$ is called a "universal predictor" when

$$\forall L \in \mathsf{R} \, \forall n>>0:s(L)\_n=\chi\_U(s(L)\_{

A famous example is [Solomonoff induction](http://www.vetta.org/documents/disSol.pdf)

It is easy to see $U \notin \mathsf{R}$ by considering $L = U^c$. The question is

> Is there a universal predictor $U \in \mathsf{P/poly}$?

More specifically

> Is Solomonoff induction in $\mathsf{P/poly}$?

It is not hard to see that a positive answer would imply $\exists A \in \mathsf{TALLY}:\mathsf{R} \subset \mathsf{E}^A$ ($A$ is s.t. $U$ is Cook-reducible to $A$ and we have $\mathsf{R} \subset \mathsf{E}^A$ since it is possible to apply $U$ to the sequence $\chi\_L(n)$ to decide $L$ in exponential time). This implication seems surprising but I don't see why it's necessarily false

EDIT: Actually such $A$ exists:

$\lbrace w | \exists i,j \in \mathbb{N} : i \in L\_j$ and $|w| = f(i,j) \rbrace$

Here $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ is a bijection computable in polynomial time and $L\_j$ is the $j$-th recursive language (I'm using an arbitrary enumeration of the recursive languages)

However a universal predictor in $\mathsf{P/poly}$ implies a stronger statement, namely, that there is $A \in \mathsf{TALLY}$ and some fixed polynomial $p(n)$ such that all languages in $\mathsf{TALLY} \cap \mathsf{R}$ can be computed in time $p(n)$ given an oracle for $A$

EDIT: The answer to the first question is positive. Showing this is equivalent to constructing a Turing machine with a special tape on which some fixed (input-independent) infinite string is written in the initial state s.t. this machine computes a universal predictor in polynomial time. To do this, imagine the special tape to be 2-dimensional. In row $i$ of the tape write infinite computable sequence number $i$ (i.e. computed by program $i$). The predictor then works as follows. Given an input of length $n$ it compares it to the first $n$ infinite computable sequences. The first sequence which matches the input is used for the prediction. If no sequence yields a match the predictor outputs $0$.

**Tags:** cc.complexity-theory, advice-and-nonuniformity

> **Comments:**
> **username_1**: What is $\mathsf{R}$ ?  
> **username_2**: The class of recursive languages, I guess.  
> **username_0**: @JanJohannsen Yes, it is the class of recursive languages  
> **username_0**: The answer to the first question is positive, I'll explain why later  

---

## 0 answers

