Random Sets in Subrecursive Hierarchies
- 1 October 1969
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 16 (4) , 621-630
- https://doi.org/10.1145/321541.321551
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 which include the elementary functions, such as the Grzegorczyk and Kleene subrecursive hierarchies.Keywords
This publication has 8 references indexed in Scilit:
- The definition of random sequencesInformation and Control, 1966
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1966
- The Kleene hierarchy classification of recursively random sequencesTransactions of the American Mathematical Society, 1966
- Classes of predictably computable functionsTransactions of the American Mathematical Society, 1963
- Theory of Formal Systems. (AM-47)Published by Walter de Gruyter GmbH ,1961
- Extension of an effectively generated class of functions by enumerationColloquium Mathematicum, 1958
- On the concept of a random sequenceBulletin of the American Mathematical Society, 1940
- Über die Existenz von sogenannten KollektivenFundamenta Mathematicae, 1939