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..
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Recursive Versus Recursively Enumerable Binary Relations.Dev K. Roy - 1993 - Studia Logica 52 (4):587 - 593.
A Construction for Recursive Linear Orderings.C. J. Ash - 1991 - Journal of Symbolic Logic 56 (2):673-683.
Nonstandard Characterizations of Recursive Saturation and Resplendency.Stuart T. Smith - 1987 - Journal of Symbolic Logic 52 (3):842-863.
Diagonalization in Double Frames.Andrzej Wiśniewski & Jerzy Pogonowski - 2010 - Logica Universalis 4 (1):31-39.
A Recursive Nonstandard Model of Normal Open Induction.Alessandro Berarducci & Margarita Otero - 1996 - Journal of Symbolic Logic 61 (4):1228-1241.
A Recursion Theoretic Analysis of the Clopen Ramsey Theorem.Peter Clote - 1984 - Journal of Symbolic Logic 49 (2):376-400.
Added to index2009-02-15
Total downloads102 ( #47,870 of 2,153,485 )
Recent downloads (6 months)16 ( #27,917 of 2,153,485 )
How can I increase my downloads?