Several results in program size complexity

Intuitively, the program size complexity of a binary string measures the amount of information in the string. Researchers have formalized this notion in a number of different ways. Here, we demonstrate similarities between some of these formulations. We also investigate in some detail the properties of Kolmogorov's complexity measure.

Authors

• Howard P. Katseff
• Michael Sipser

Keywords

No keywords are indexed for this paper.