Proof that dynamical systems with bounded Kolmogorov complexity can't emulate all Turing machines

Question

Motivation:

During a discussion with neuroscientists the question arose as to whether the human brain may emulate any Turing machine. If we assume that animal brains may be modelled as deterministic dynamical systems with variable complexity then it’s reasonable to suppose that some brains may be capable of emulating more powerful Turing machines than others.

After some reflection, it occurred to me that if there is a Universal Turing machine among the machines that can be emulated then for a particular set of initial conditions the average Kolmogorov complexity of the dynamical system must be an increasing function of time. For concreteness, by a brain given initial conditions, I mean a human brain coupled with an environment which has a particular initialisation.

This environment could be a book full of math problems ordered by their Kolmogorov complexity, i.e. a sequence of decidable problems, so the sequence of states of the dynamical system may be a sequence of Turing machines that solve decidable problems of increasing complexity.

Note: I'd like to clarify that the brains in question are dynamical systems, i.e. mathematical idealisations, that may accept arbitrarily large inputs so they have unbounded memory. Furthermore, by emulate a Turing machine I mean that the dynamical system may simulate a Turing Machine that solves a decidable problem. As there are countably many decidable problems and just as many Turing machines, each TM may be identified with a string that encodes a natural number.

Problem:

Might there be an elementary proof that discrete dynamical systems with bounded Kolmogorov complexity can't emulate all Turing machines? To clarify what I mean, I shall use the notation in [2].

If the history of the discrete system $f$ up to time $t \in \mathbb{N}^*$ is given by $f(t)=\{\sigma_i\}_{i=1}^t \in \{0,1\}^*$ then the system has bounded Kolmogorov Complexity if:

\begin{equation} \exists C \in \mathbb{N}\forall n \in \mathbb{N}^*, \mathbb{E}\Big[\frac{\sum_{i=1}^n K(\sigma_i)}{n}\Big] < C \tag{*} \end{equation}

where $K(\cdot)$ denotes the Kolmogorov Complexity.

The coupled dynamical system is defined as follows:

\begin{equation} \begin{cases} o_t \sim \mathcal{B}\\ f(o_t) = \sigma_t\\ \end{cases} \tag{1} \end{equation}

Each $\sigma_t$ corresponds to a Turing machine that solves a decidable problem $o_t$ sampled from a book of decidable problems $\mathcal{B}$ and if we denote the minimal length Turing Machine that solves $o \in \mathcal{B}$ by $\mathcal{M}_o$ the initial conditions $o_1$ may be sampled from the following Universal distribution on $\mathcal{B}$ [3]:

\begin{equation} Z = \sum_{o \in \mathcal{B}} 2^{-K(\mathcal{M}_o)} \tag{2} \end{equation}

\begin{equation} P(q \in \mathcal{B}) = \frac{2^{-K(\mathcal{M}_q)}}{Z} \tag{3} \end{equation}

which has a bias towards simpler problems.

If the dynamical system emulates $\sigma_t$ that decides $o_t$ the book proposes a harder problem $o_{t+1}$ sampled uniformly from $\mathcal{O}$ where:

\begin{equation} \mathcal{O} = \{o \in \mathcal{B}: K(\sigma_t) \leq K(\mathcal{M}_o) \leq 2 \cdot K(\sigma_t) \} \tag{4} \end{equation}

Otherwise, $\mathcal{B}$ replaces $o_t$ with a problem of lower associated Kolmogorov complexity. This list of simpler problems is finite and if $f$ can’t produce $\sigma_t$ that decides any of the problems in this stack the dynamical system simply continues running $\sigma_t$ indefinitely so $\forall l \geq t+1, \sigma_l= \sigma_t$.

Now, my claim is that if $(*)$ is true then the system can only emulate a finite number of Turing machines. I suspect that this must be true but when I checked related work such as [1] by Hector Zenil I couldn't find a reference to the theorem I was looking for.

References:

1. H. Zenil. Asymptotic Behaviour and Ratios of Complexity in Cellular Automata Rule Spaces. International Journal of Bifurcation and Chaos vol. 23, no. 9, 2013.
2. Corominas-Murtra B, Luís F. Seoane, Solé R. 2018 Zipf’s Law, unbounded complexity and open-ended evolution. J. R. Soc. Interface 15: 20180395.
3. Marcus Hutter et al. (2007) Algorithmic probability. Scholarpedia, 2(8):2572.

Answer 1

This is really a comment but it is too long for a comment. I think that you need to clarify your question. If I understand correctly, you're positing some discrete-time process that generates a finite string $\sigma_t$ at time $t$, and by "bounded Kolomogorov complexity" you mean that the Kolmogorov complexity of the strings up to time $t$ is at most $Ct$ for some absolute constant $t$. What's unclear is what you mean by "emulate a Turing machine."

Trivially, we could set $\sigma_1$ equal to a description of a Universal Turing machine, which can simulate any other Turing machine. That can't be what you mean.

So maybe you're thinking of $\sigma_t$ as being the contents of the tape of a Turing machine at time $t$, and you're wondering whether the condition of bounded Kolmogorov complexity means that the sequence of tape contents can only come from finitely many different Turing machines? But now it's unclear what you mean by "arbitrary initial conditions." Does this mean that $\sigma_1$ is "arbitrary"? But if $\sigma_1$ is an arbitrary string then its Kolmogorov complexity is unbounded. So maybe you mean that $\sigma_1$ is arbitrary, subject only to the condition that its Kolmogorov complexity is at most $C$? But now consider the family $\{\Sigma_n\}$ where $$\Sigma_n(t) = (\sigma_{n,1}, \sigma_{n,2}, \ldots, \sigma_{n,t})$$ is defined by letting $$\sigma_{n,t} = \cases{1, &if $t=n$;\cr 0, &otherwise.}$$ Certainly the Kolmogorov complexity of $\Sigma_n(t)$ is bounded by $Ct$, but we're "emulating" infinitely many Turing machines (starting with an empty tape). Unless by "emulating" you mean something else?