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.
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.
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}\).
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.
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.