Additional Key Words and Phrases: computational complexity, sequences, random sequences, Turing machines
Selected papers that cite this one
- Gregory J. Chaitin. On the simplicity and speed of programs for computing infinite sets of natural numbers. Journal of the ACM, 16(3):407-422, July 1969.
- Robert P. Daley. An example of information and computation resource trade-off. Journal of the ACM, 20(4):687-695, October 1973.
- Martin Dowd. Generic oracles, uniform machines, and codes. Information and Computation, 96(1):65-76, January 1992.
- Aaron Shenhar. On the Kolmogorov complexity of arbitrary objects. Journal of Complexity, 9(4):499-517, December 1993.
- Ludwig Staiger. Kolgomorov complexity and Hausdorff dimension. Information and Computation, 103(2):159-194, April 1993.
- V. A. Uspensky and A. Shen. Relations between varieties of Kolmogorov complexities. Mathematical Systems Theory, 29(3):271-292, May/June 1996.
- David G. Willis. Computational complexity and probability constructions. Journal of the ACM, 17(2):241-259, April 1970.
Selected references
- Gregory J. Chaitin. On the length of programs for computing finite binary sequences. Journal of the ACM, 13(4):547-569, October 1966.
- Per Martin-Löf. The definition of random sequences. Information and Control, 9(6):602-619, December 1966.