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 $A$ be a finite set (hereby called an alphabet) and consider the set $W$ of all finite sequences of elements of $A$ (hereby called words). I will use $l e n (w)$ to denote the length of a word $w \in W$ .

I will call any partial function of the form $P : W \to W$ as a finite abstract computer, and I will call the domain $D (P)$ of a finite abstract computer as the set of all admissible programs in $P$ . In this context a word $w \in 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_{Q} a$ .

The relative complexity of a word $w \in W$ with respect to a finite abstract computer $P$ is defined as $r e l (w, P) := min {l e n (v) ∥ v \in D (P) 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 $r e l (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 W} ∥ r e l (w, P) - r e l (w, Q) ∥ \leq c$ Now, if we define the distance between two finite abstract computers as $d (P, Q) = sup_{w \in W} ∥ r e l (w, P) - r e l (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 D (P)$ and $w_{P} \in 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 $r e l (v, Q) \leq l e n (w_{Q}) + r e l (v, P) and r e l (v, P) \leq l e n (w_{P}) + r e l (v, Q)$ We get the inequality for $r e l (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 $r e l (v, P)$ . Note that the inequalities hold even when $v$ is not computable via $P$ or via $Q$ . This easily leads to the inequality $∥ r e l (v, P) - r e l (v, Q) ∥ \leq max {l e n (w_{P}), l e n (w_{Q})}$ for every $v \in W$ . Then we preserve the inequality when we take the supremum over all $w \in W$ .

An example

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

A counter-example for the converse

Let $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.