The Kleene hierarchy classification of recursively random sequences

The Kleene hierarchy classification of recursively random sequences
HTML articles powered by AMS MathViewer

Trans. Amer. Math. Soc. 125 (1966), 497-510

DOI: https://doi.org/10.1090/S0002-9947-1966-0207562-2

PDF | Request permission

References

Alonzo Church, On the concept of a random sequence, Bull. Amer. Math. Soc. 46 (1940), 130–135. MR 911, DOI 10.1090/S0002-9904-1940-07154-X
Martin Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR 0124208
K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro, Computability by probabilistic machines, Automata studies, Annals of Mathematics Studies, no. 34, Princeton University Press, Princeton, N.J., 1956, pp. 183–212. MR 0079550
J. L. Doob, Note on probability, Ann. of Math. (2) 37 (1936), no. 2, 363–367. MR 1503284, DOI 10.2307/1968449
William Feller, An introduction to probability theory and its applications. Vol. I, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1957. 2nd ed. MR 0088081
Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
Konrad Knopp, Theory of Functions. II. Applications and Continuation of the General Theory, Dover Publications, New York, 1947. MR 0019722

Recursively random sequences

Donald Loveland, A new interpretation of the von Mises’ concept of random sequence, Z. Math. Logik Grundlagen Math. 12 (1966), 279–294. MR 205293, DOI 10.1002/malq.19660120124
Werner Markwald, Ein Satz über die elementararithmetischen Definierbarkeitsklassen, Arch. Math. Logik Grundlag. 2 (1956), 78–86 (German). MR 78929, DOI 10.1007/BF01969993
Richard von Mises, Probability, statistics and truth, The Macmillan Company, New York, 1957. Second revised English edition, prepared by Hilda Geiringer. MR 0090158
Hilary Putnam, Trial and error predicates and the solution to a problem of Mostowski, J. Symbolic Logic 30 (1965), 49–57. MR 195725, DOI 10.2307/2270581
Hartley Rogers Jr., Computing degrees of unsolvability, Math. Ann. 138 (1959), 125–140. MR 114752, DOI 10.1007/BF01342939

Die Widerspruchsfreiheit des Kollectiv-begriffes der Wahrscheinlichkeitsrechnung