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