Can the halting problem be solved if one could compute program-size complexity?
The answer is yes, and here is a sharper and more elegant version of my proof.
LEMMA. If an n-bit program p halts, then the time t it takes to halt satisfies H(t) ≤ n + c. So if p has run for time T without halting, and T has the property that t ≥ T implies H(t) > n + c, then p will never halt.
Consider the r.e. set of all true upper bounds on H: the set of all true upper bounds {H(x) ≤ k} is recursively enumerable. Imagine enumerating this set, and keep track of the time. Assuming that H is computable, compute H(x) for each n-bit string x. Then enumerate {H(x) ≤ k} until we get the best possible upper bound on H(x) for all n-bit strings x. Let β(n) be defined to be the time it takes to enumerate enough of the set of all true upper bounds on program-size complexity until one obtains the correct value of H(x) for all n-bit strings x. If one is given n and β(n) or any number greater than β(n), one can use this to determine an n-bit bit string xmax with maximum possible complexity H(xmax) = n + H(n) + O(1). Thus any number k ≥ β(n) has
n + H(n) − c' < H(xmax) ≤ H(k) + H(n) + c''and
H(k) > n − c' − c''.Thus we can use β(n), which is computable from H, with the LEMMA to solve the halting problem as follows: an n-bit program p halts iff it halts before time β(n + c + c' + c'').
With thanks for stimulating discussions to Cris Calude and George Markowsky.
G. J. Chaitin, 26 July 1995