… proved without reference to infinity and the empty string.
Some readers have objected to my simple proof that computable transformation of a binary string can result in an infinite increase of algorithmic specified complexity (ASC). Here I give a less-simple proof that there is no upper bound on the difference in ASC of and To put it more correctly, I show that the difference can be any positive real number.
Updated 12/8/2019: The assumptions of my theorem were unnecessarily restrictive. I have relaxed the assumptions, without changing the proof.
Definitions. Let the set of all binary strings. For all in the algorithmic specified complexity of is defined
where is an element of and is a distribution of probability over Here is the algorithmic complexity of conditioned on
Theorem. Let be a constant function on Let and be elements of for which holds. Also let be a positive real number. There exists a distribution of probability over such that
[12/8/2019: To generalize, replace the first two sentences of the theorem with the following: Let be an element of and let and be elements of such that Let be a computable function on with ]
Proof. Noting that by hypothesis,
where and In the case of set and solve for in terms of :
Observe that is precisely equal to if and only if and is strictly less than when Thus distributes probability mass
over the nonempty set excluding and In the case of set and similarly solve for in terms of QED.