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


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)_{<n})$$

A famous example is Solomonoff induction

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$.

  • $\begingroup$ What is $\mathsf{R}$ ? $\endgroup$ – Jan Johannsen Feb 27 '13 at 9:36
  • 1
    $\begingroup$ The class of recursive languages, I guess. $\endgroup$ – MassimoLauria Feb 27 '13 at 9:48
  • $\begingroup$ @JanJohannsen Yes, it is the class of recursive languages $\endgroup$ – Vanessa Feb 28 '13 at 20:33
  • $\begingroup$ The answer to the first question is positive, I'll explain why later $\endgroup$ – Vanessa Mar 1 '13 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.