3
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ The definitions of bounded complexity in [2] seem different from your (*). Is this intentional? If $\Sigma(t)$ is a sequence and not a set (as it is in [2]), then (*) can never be true because there are only finitely many sequences with Kolmogorov complexity below $C$ but the $\Sigma(t)$ are all distinct. $\endgroup$ – Ilkka Törmä Dec 30 '19 at 10:50
  • $\begingroup$ @IlkkaTörmä That is a good point. I should normalise the complexity term. $\endgroup$ – Aidan Rocke Dec 30 '19 at 11:22
  • 3
    $\begingroup$ A cellular automaton is an unbounded grid that evolves according to certain rules. We don't have unbounded grids in our brains, so the same problem applies. $\endgroup$ – provocateur Dec 30 '19 at 12:53
  • 1
    $\begingroup$ I don't think talking about universal computing machines and outsourcing the computation to the environment helps. At the end of the day, even given some sort of universal computing machine, you still need to input some parameter p to tell the machine to run the pth Turing machine. If the brain isn't big enough to accommodate p, then that will not be possible. $\endgroup$ – provocateur Dec 30 '19 at 13:25
  • 1
    $\begingroup$ I don't claim that I can fully understand your question but in my interpretation the human brain can of course simulate a universal (or any other) Turing-machine. Also, if your discrete system evolves according to some rule, i.e., $\sigma_t$ is computable from $\Sigma_{t-1}$, then $K(\Sigma(t))<C+\log t$. $\endgroup$ – domotorp Dec 30 '19 at 13:59
3
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for asking this question. By emulate a Turing machine, I mean that the dynamical system may be used to solve a decidable problem. By extension, emulating all Turing machines would be equivalent to solving all decidable problems. $\endgroup$ – Aidan Rocke Dec 30 '19 at 21:02
  • $\begingroup$ @AidanRocke : Decidable problems have arbitrarily large (and complex) inputs. How are these specified, in light of your bound on Kolmogorov complexity? $\endgroup$ – Timothy Chow Dec 31 '19 at 3:07
  • $\begingroup$ Each decision problem may be identified with a natural number and after further reflection I decided to sample the initial condition from a distribution which is biased towards simpler problems. $\endgroup$ – Aidan Rocke Dec 31 '19 at 9:06
  • $\begingroup$ I think my modification of (*) and the other revisions I have made address all remaining issues. Would you agree? $\endgroup$ – Aidan Rocke Dec 31 '19 at 11:05
  • $\begingroup$ @AidanRocke : I'm afraid I can't follow your explanations. At one point you say that $o_t$ is a "decidable problem" but later you refer to $o_1$ as "initial conditions." At one point you say that $\mathcal B$ is a "book" (set?) of decidable problems but then later you say $\mathcal B$ "replaces" $o_t$ with something else–so it sounds like you're conflating $\mathcal B$ with a sequence of random samples from $\mathcal B$? Also I don't understand what it means for a dynamical system to "solve" $o_t$. This is just the beginning of my confusions. $\endgroup$ – Timothy Chow Dec 31 '19 at 18:29

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.