
Accession Number : AD0672718
Title : RANDOM SETS IN SUBRECURSIVE HIERARCHIES,
Corporate Author : RAND CORP SANTA MONICA CALIF
Personal Author(s) : DiPaola,R. A.
Report Date : JUL 1968
Pagination or Media Count : 26
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)
Descriptors : (*MATHEMATICAL LOGIC, *SET THEORY), RECURSIVE FUNCTIONS, SEQUENCES(MATHEMATICS), AUTOMATA, INFORMATION THEORY, THEOREMS
Subject Categories : Theoretical Mathematics
Cybernetics
Distribution Statement : APPROVED FOR PUBLIC RELEASE