Additional Key Words and Phrases: minimal programs, limiting recursion, function identification, inductive inference, degree of unsolvability, Kleene hierarchy, program properties, program length measures
Selected references
- Manuel Blum. On the size of machines. Information and Control, 11(3):257-265, September 1967.
- Jerome Feldman. Some decidability results on grammatical inference and complexity. Information and Control, 20(3):244-262, April 1972.
- Per Martin-Löf. The definition of random sequences. Information and Control, 9(6):602-619, December 1966.
- David Pager. On the problem of finding minimal programs for tables. Information and Control, 14(6):550-554, June 1969.
- R. J. Solomonoff. A formal theory of inductive inference. part I. Information and Control, 7(1):1-22, March 1964.
- R. J. Solomonoff. A formal theory of inductive inference. part II. Information and Control, 7(2):224-254, June 1964.
- David G. Willis. Computational complexity and probability constructions. Journal of the ACM, 17(2):241-259, April 1970.