Abstract

Loveland and Meyer have studied necessary and sufficient conditions for an infinite binary string x to be recursive in terms of the programsize complexity relative to n of its n-bit prefixes xn. Meyer has shown that x is recursive iff ∃c, ∀n, K(xn/n) ≤ c, and Loveland has shown that this is false if one merely stipulates that K(xn/n) ≤ c for infinitely..