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

A computable predictor is an algorithm $A$ computing a function $f_A : \{0,1\}^* \rightarrow \{0,1\}$. We regarding the function as providing a predicted continuation of a finite binary sequence. We define an infinite binary sequence $\alpha \in \{0,1\}^\omega$ to be comprehensible for $A$ when

$$\exists n > 0 \, \forall m > n \, f_A(\alpha_{<m})=\alpha_m$$

i.e. sufficiently late in the sequence, $A$ always predicts $\alpha$ correctly.

Obviously $\alpha$ can only be comprehensible when it's computable. It's also easy to see that for any computable predictor $A$, $\exists \alpha$ computable s.t. $\alpha$ is not comprehensible for $A$. For example, we can define $\alpha$ recursively by

$$\alpha_{n} := \lnot f_A(\alpha_{<n})$$

On the other hand, it is possible to define $p : \{0,1\}^* \rightarrow \{0,1\}$ uncomputable s.t. all computable sequences are comprehensible for $p$. For example, $p(x)$ can be defined to be $\alpha_{|x|}$ where $\alpha$ is the minimal Kolmogorov complexity infinite sequence satisfying $\alpha_{<|x|} = x$.

So, it is impossible to construct a universal computable predictor, but we can try to make it "approximately universal". Formally, an infinite sequence of computable predictors $\{A_n\}_{n \in \mathbb{N}}$ is called asymptotically universal when $\forall \alpha \in \{0,1\}^\omega$ computable $\exists n > 0 \, \forall m > n: \alpha$ is comprehensible for $A_m$. It is easy to construct an example of such a sequence. Namely, define $A_n(x)$ to be the following program: "Run the first $n$ programs producing infinite sequences by dovetailing. The first time one of those programs produces output $y$ s.t. $|y| = |x| + 1$ and $y_{<|x|} = x$, terminate and produce the output $y_{|x|}$. If all of the programs produced outputs of length > $|x|$ and neither satisfied the condition, terminate and produce the output $0$".

Suppose $A_n$ from the above example is a run on $\alpha \in \{0,1\}^\omega$ produced by an algorithm $B$. For $n >> 0$ the time of the computation of $A_n(\alpha_{<k})$ is bounded by $p(t(k), 2^{|B|})$ where $t$ is the time complexity of $B$ and $p$ is polynomial. That is:

$$\forall B \, \exists n \, \forall N > n \, \forall k: T(A_N(\alpha(B)_{<k})) < p(t(k), 2^{|B|})$$

It seems natural to ask whether this can be improved. Specifically, we define an asymptotically universal sequence of computable predictors $\{E_n\}_{n \in \mathbb{N}}$ to be efficient when the time of the computation $E_n(\alpha_{<k})$ as above can be bounded by $q(t(k),|B|)$ with $q$ polynomial, given $n >> 0$. The question is thus

Is there an efficient asymptotically universal sequence of computable predictors?

share|cite|improve this question

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.