Additional Key Words and Phrases: computational complexity, prediction, induction, inductive inference, probability, axiomatic probability theory, automata, Turing machines, information, information theory, artificial intelligence
Selected papers that cite this one
- Gregory J. Chaitin. Information-theoretic limitations of formal systems. Journal of the ACM, 21(3):403-424, July 1974.
- L. K. Schubert. Iterated limiting recursion and the program minimization problem. Journal of the ACM, 21(3):436-445, July 1974.
- Aaron Shenhar. On the Kolmogorov complexity of arbitrary objects. Journal of Complexity, 9(4):499-517, December 1993.
- Ray J. Solomonoff. The discovery of algorithmic probability. Journal of Computer and System Sciences, 55(1):73-88, August 1997.
Selected references
- Manuel Blum. A machine-independent theory of the complexity of recursive functions. Journal of the ACM, 14(2):322-336, April 1967.
- Gregory J. Chaitin. On the length of programs for computing finite binary sequences. Journal of the ACM, 13(4):547-569, October 1966.
- Gregory J. Chaitin. On the length of programs for computing finite binary sequences: Statistical considerations. Journal of the ACM, 16(1):145-159, January 1969.
- Milton W. Green. A lower bound on rado's sigma function for binary turing machines. In Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, pages 91-94, Princeton, New Jersey, 11-13 November 1964. IEEE.
- Per Martin-Löf. The definition of random sequences. Information and Control, 9(6):602-619, December 1966.
- R. J. Solomonoff. A formal theory of inductive inference. part I. Information and Control, 7(1):1-22, March 1964.
- R. E. Stearns, J. Hartmanis, and P. M. Lewis II. Hierarchies of memory limited computations. In Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pages 179-190. IEEE, 1965.