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

CC BY-SA 4.0
2021-04-13T05:04:59.933Z
2021-04-13T05:04:59.933Z
Xi Li
<p>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>

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

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

<p>If we replace:</p>

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

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

<p><strong>Question:</strong> Is there any work or related theory that extends the complexity measure elegantly to dynamical systems?</p>

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

<p>Thanks.</p>

<reference-request><kolmogorov-complexity>
How to extend Solomonoff Induction to continuous domain
Kh40tiK
# How to extend Solomonoff Induction to continuous domain

(Asked by: username_0 on 2017-04-14)

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.

Thanks.

**Tags:** reference-request, kolmogorov-complexity

---

## 1 answers

### Answer by username_1 on 2021-04-13. Score: 1

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.


---

