I’m still working on this, but it looks like if K(x) < K(y), on a given UTM, where K(x) denotes the Kolmogorov complexity of the string x, there’s no guarantee, absent additional assumptions, that K(x) < K(y) on some other UTM. This is a big deal if true, because the difference in the Kolmogorov Complexities across two UTMs is always bounded by a constant, suggesting universality. But if the ordinal ranking of complexities is not generally preserved across UTMs, then we can’t say it’s truly universal. It looks like the answer is that for sufficiently different strings where |K(x) – K(y)| is large, then order is preserved, but still, this is a big deal that I’ve never seen mentioned anywhere. I’ll follow up shortly with a proof if it’s actually correct.

UPDATE: Here’s the proof so far.

Complexity on Different UTMs: Many machines are mathematically equivalent to a UTM, and as a consequence, there are multiple UTMs. For example, Charles Babbage’s Analytical Engine is a UTM, and so are basically all personal computers.

However, there’s a simple lemma that proves the difference between K(x) for any two UTMs is bounded by a constant C that does not depend upon x.

Example: Let’s assume that both Octave and Python are “Turing Complete”, which means you can calculate any function, or more generally run any program, that you can run on a UTM in both Octave and Python. Anything you can run on a UTM is called a “computable function”.

This means (arguendo) that any computable function can be implemented in both Octave and Python, which is probably true.

The compilers for both Octave and Python are themselves computable functions. This means that we can write a Python compiler in Octave, and vice versa. As a consequence, given a program written in Python, we can compile that program in Octave, using a single, universal compiler for Python code that runs in Octave. This code will have a fixed length C.

Let KO(x) and KP(x) denote length of the shortest program that generates x as output in Octave and Python, respectively, and assume that y is the shortest Python program that generates x, so that KP(x) = |y|.

Because we have a compiler for Python code that runs in Octave, we can generate x given y and that compiler, which together will have a length of,

KP(x) + C ≤ KO(x).

Said in words, the complexity of x in Octave can’t be greater than the complexity of the Python program that generates x, plus the Python compiler that runs in Octave, for all x.

Further, this argument would apply to any pair of Turing Complete languages, which implies the following general result:

K1(x) + C ≤ K2(x), Eq. (1)

where C is a constant that does not depend upon x, and K1(x) and K2(x) are the Kolmogorov Complexities of x in two distinct Turing Complete languages.

Consistency of Ordinality: Ideally, the ordinal rankings of strings in terms of their complexities would be consistent across UTMs, so that if K1(x) < K1(y), then K2(x) < K2(y). If true, this would allow us to say that x is less complex than y, on an objective basis, across all UTMs.

This is the case, subject to a qualification:

Assume that K1(x) < K1(y). Eq. (1) implies that,

K1(x) ≤ K2(x) + C; and

K1(y) ≤ K2(y) + C, for exactly the same value of C.

This in turn implies that,

K1(x) = K2(x) + c_x; and

K1(y) = K2(y) + c_y, for some c_x, c_y ≤ C.

That is, Eq. (1) implies that there must be some exact values for c_x and c_y that are both bounded above by C, and possibly negative.

We have then that,

K2(x) = K1(x) – c_x; and

K2(y) = K1(y) – c_y.

Because we assumed K1(x) < K1(y), if c_y ≤ c_x, then the result is proven. So assume instead that c_x ≤ c_y. Now set,

c_x = K1(x) – K1(y) + c_y, which implies that

K2(x) = K1(x) – K1(x) + K1(y) – c_y = K2(y).

As a consequence, for any c, such that c_x < c ≤ C, it must be the case that K1(x) – c = K2(x) < K2(y), which is exactly the desired result. Simplifying, we have the following constraint, satisfaction of which will guarantee that K2(x) < K2(y), noting that |c_y – c_x| < C:

C < K1(y) – K1(x). Eq. (2)

Said in words, if we know that the difference in complexities between strings x and y, exceeds the complexity of the translator compiler between the machines, then their ordinal relationships are preserved. However, this means that ordinality could be sensitive to differences in complexity that are small relative to the compiler.

UPDATE 2:

It just dawned on me, the Halting Problem is a physical problem, that cannot be answered, because of decidability, not because of some mechanical limitation. That is, there is a logical contradiction, which precludes existence. Because UTMs are physically real, we have a mathematical result that proves the non-existence of some physical system, specifically, a machine that can solve the Halting Problem.