RANDOM SETS IN SUBRECURSIVE HIERARCHIES,
Abstract
Successive modifications of Church's definition of a random sequence are considered in terms of their relative position in the Ritchie hierarchy of Kalmar elementary functions. A general result is derived governing the classification of Church random sequences in subrecursive hierarchies that include the elementary functions, such as the Grzegorczyk and Kleene subrecursive hierarchies. This study extends recent work done elsewhere directed toward the use of the theory of recursive functions in making precise the notion of a random sequence and the information content of a discrete set of objects. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1968
- Accession Number
- AD0672718
Entities
People
- R. A. Dipaola
Organizations
- RAND Corporation