A Simple Problem in Kolmogorov-Chaitin Complexity

A simple problem in Kolmogorov-Chaitin complexity

This post is inspired by two old posts (this and that) on Good Math, Bad Math by Mark Chu-Carroll. It is just that I am a mathematician, and I need to dot all the i’s and cross all the t’s. Besides, I learn better when I write things.

Description of the problem

Let $\mathcal{A}$ be a finite set (hereby called an alphabet) and consider the set $\mathcal{W}$ of all finite sequences of elements of $\mathcal{A}$ (hereby called words). I will use $len(w)$ to denote the length of a word $w\in \mathcal{W}$.

I will call any partial function of the form $P\colon \mathcal{W}\to \mathcal{W}$ as a finite abstract computer, and I will call the domain $\mathcal{D}(P)$ of a finite abstract computer as the set of all admissible programs in $P$. In this context a word $w\in \mathcal{W}$ is computable via $P$ if $w$ is in the range of $P$.

I will say that a finite abstract computer $P$ emulates another finite abstract computer $Q$ if there is a fixed admissible program $w_Q$ in $P$ such that for every admissible program $a$ in $Q$ the word $w_Q a$ is an admissible program in $P$ and we get \[ Q(a) = P(w_Q a) \] Here the concatenation of word $w_Q$ and $a$ is denoted by $w_Qa$.

The relative complexity of a word $w\in \mathcal{W}$ with respect to a finite abstract computer $P$ is defined as \[ rel(w,P) := \min\{len(v)\|\ v\in\mathcal{D}(P)\text{ and }P(v) = w\} \] In other words, the relative complexity of a word $w$ is the length of a shortest admissible program in $P$ which generates $w$. If there is no such word then $rel(w,P)$ is defined to be $-1$.

Now, take two finite abstract computers $P$ and $Q$. Today, I would like to show that if $P$ and $Q$ emulate each other then there exists a constant $c$ such that \[ \sup_{w\in \mathcal{W}} \|rel(w,P)-rel(w,Q)\| \leq c \] Now, if we define the distance between two finite abstract computers as \[ d(P,Q) = \sup_{w\in\mathcal{W}} \|rel(w,P)-rel(w,Q)\| \] we see that the statement above can be rephrased as follows:

If $P$ and $Q$ can emulate each other then the distance $d(P,Q)$ is finite.

Or, equivalently

If the distance between two finite abstract computers is infinite then one of these machines can not emulate the other.

Though, I have to say that $d$ is not really a distance in the sense of a metric space as I will mention at the end.

A proof of the statement

Assume $P$ and $Q$ emulate each other, and respectively let $w_Q\in \mathcal{D}(P)$ and $w_P\in\mathcal{D}(Q)$ be the admissible programs emulating $Q$ in $P$ and $P$ in $Q$. Take a word $v$ which is computable via both $P$ and $Q$. Then we can easily see that \[ rel(v,Q) \leq len(w_Q) + rel(v,P) \quad\text{ and }\quad rel(v,P) \leq len(w_P) + rel(v,Q) \] We get the inequality for $rel(v,Q)$ because for any admissible program $a$ in $P$ with the property that $v=P(a)$ (recall that $v$ is computable via $P$) then we have $v=Q(w_P a)$. Conversely, since $v$ is also computable via $Q$ we have the similar inequality for $rel(v,P)$. Note that the inequalities hold even when $v$ is not computable via $P$ or via $Q$. This easily leads to the inequality \[ \|rel(v,P) - rel(v,Q)\| \leq \max\{len(w_P),len(w_Q)\} \] for every $v\in \mathcal{W}$. Then we preserve the inequality when we take the supremum over all $w\in\mathcal{W}$.

An example

Let $\mathcal{A}$ contain a single letter $1$. So, the set of words in $\mathcal{A}$ is naturally isomorphic to the set of natural numbers. Now, I will define $P(n) = 2n$ and $Q(n) = 3n$ for every $n\in\mathbb{N}$. Notice that $rel(n,P)=-1$ if $n$ is not even, and $rel(n,P)=(n/2)$ when $n$ is even. Similarly, $rel(n,Q)=-1$ when $n$ is not divisible by 3, and $rel(n,Q)=(n/3)$ if $n$ is divisible by 3. It is easy to see that \[ \sup_{n\in\mathbb{N}} \|rel(n,P)-rel(n,Q)\| = \infty \] Thus one of these finite abstract computers can not emulate the other.

A counter-example for the converse

Let $\mathcal{A}$ be as before and define $P(2^n)=1$ whenever $n$ is a prime and define $Q(3^n)=1$ whevever $n$ is a prime. Clearly, $P$ and $Q$ are both partial functions. It takes a little work (some number theory) to show that $P$ can not emulate $Q$ and vice versa. On the other and $d(P,Q)=0$ which is finite. Also notice that the distance is 0 while $P\neq Q$. That is the function $d$ defined above is not really a metric in the strict mathematical sense.