Accession Number:

AD0672718

Title:

RANDOM SETS IN SUBRECURSIVE HIERARCHIES,

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CALIF

Personal Author(s):

• DiPaola,R. A.

Report Date:

1968-07-01

Pagination or Media Count:

26.0

Abstract:

Successive modifications of Churchs 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