Take the 2-minute tour ×
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.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.