Information- theoretic characterizations of recursive infinite strings


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..



    Upload a copy of this work     Papers currently archived: 77,985

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

Similar books and articles

Effective coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Hyper-Torre isols.Erik Ellentuck - 1981 - Journal of Symbolic Logic 46 (1):1-5.
A construction for recursive linear orderings.C. J. Ash - 1991 - Journal of Symbolic Logic 56 (2):673-683.
Recursive Analysis.R. L. Goodstein - 1961 - Dover Publications.
A recursion theoretic analysis of the clopen Ramsey theorem.Peter Clote - 1984 - Journal of Symbolic Logic 49 (2):376-400.


Added to PP

118 (#110,912)

6 months
1 (#485,425)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references