Information-theoretic characterizations of recursive infinite strings

Abstract

Loveland and Meyer have studied necessary and sufficient conditions for an infinite binary string x to be recursive in terms of the program-size complexity relative to n of its n-bit prefixes xn. Meyer has shown that x is recursive iff ∃c, ∀n, K(xn{plus 45 degree rule}n) ≤ c, and Loveland has shown that this is false if one merely stipulates that K(xn{plus 45 degree rule}n) ≤ c for infinitely many n. We strengthen Meyer's theorem. From the fact that there are few minimal-size programs for calculating n given result, we obtain a necessary and sufficient condition for x to be recursive in terms of the absolute program-size complexity of its prefixes: x is recursive iff ∃c, ∀n, K(xn) ≤ K(n) + c. Again Loveland's method shows that this is no longer a sufficient condition for x to be recursive if one merely stipulates that K(xn) ≤ K(n) + c for infinitely many n. © 1976.