Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.