Algorithmic complexity
Marcus Hütter · Scholarpedia · 2008
The information content or complexity of an object can be measured by the length of its shortest description.For instance the string "01010101010101010101010101010101" has the short description "16 repetitions of 01", while "11001000011000011101111011101100" presumably has no simpler description other than writing down the string itself.More formally, the Algorithmic "Kolmogorov" Complexity (AC) of a string is defined as the length of the shortest program that computes or outputs , where the program is run on some fixed reference universal computer.Contents 1 Overview 2 Kolmogorov complexity 3 Prefix complexity 3.1 Prefix Turing machine 3.2 Universal prefix Turing machine 3.3 Prefix complexity 4 Properties of prefix complexity 4.1 Explanation 4.2 Proof ideas 5 Other complexities and related concepts 6 History 6.1 Kolmogorov complexity 6.2 Other complexities and related concepts 6.3 Resource-bounded complexity 7 References 8 Recommended reading 9 External links 10 See also Kolmogorov complexity resource page (http://www.hutter1.net/kolmo.htm)(introductions