Informally speaking, Solomonoff Induction provides an Bayesian optimal way to predict the next symbol from observed symbol sequences $S_1S_2S_3...S_n$ where each $S_i$ belongs to a finite symbol set $\Sigma$. To get the posterior probability distribution of the next symbol, we make a weighted average prediction of all Turing Machines that produces first $n$ symbols. For each Turing Machine $M$ within consideration, the weight would be inverse exponential of "complexity" of that Turing Machine.

$$p(M) = 2^{-L(M)}$$

Where $L(M)$ is the description length of $M$ in context of an universal Turing Machine $U$.

If we replace:

  • finite symbol set $\Sigma$ to continuous domain $D$, such as $R^n$.
  • Symbol sequence $S_i$ to discrete time series, for example $x_1x_2x_3...x_n$ where $x_i \in D$
  • Turing Machine $M$ to discrete time dynamical system, for example $x_{n+1} = f(x_n)$, which is mapping $R^n \to R^n$

The Bayesian inference would still work in this case, however we have to redefine the complexity measure $p(f) \to [0, \infty)$, which is probability density function of $f$.

Question: Is there any work or related theory that extends the complexity measure elegantly to dynamical systems?

I would also be interested in results for continuous dynamical systems, in terms of differential equations.



The set of computable real functions is also recursively enumerable. Assume it is enumerated by $(f_i)_{i\in\omega}$. Then the Solomonoff prior of $f_i$ is $p(f_i)=2^{-K(i)}$. So there is no difference whether the function is defined over natural numbers or real numbers, as long as it is computable.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.