Kolmogorov complexity: Difference between revisions

Revision as of 22:57, 15 October 2004

Revision as of 13:32, 14 November 2004

Line 1:

[[zh:算法信息论]]

'''Algorithmic information theory''' is a field of study which attempts to capture the concept of complexity by using tools from theoretical computer science. The chief idea is to define the complexity (or '''Kolmogorov complexity''') of a [[string]] as the length of the shortest program which outputs that string. Strings that can be produced by short programs are considered to be not very complex. This notion is surprisingly deep and can be used to state and prove impossibility results akin to [[Gödel's incompleteness theorem]] and [[halting problem|Turing's halting problem]].

Line 50 ⟶ 48:

* [http://www.csse.monash.edu.au/~dld David Dowe]'s [http://www.csse.monash.edu.au/~dld/MML.html Minimum Message Length (MML)] and [http://www.csse.monash.edu.au/~dld/Occam.html Occam's razor] pages.

* [http://nms.lcs.mit.edu/~gch/kolmogorov.html Kolmogorov Complexity] provides a simple explanation of Kolmogorov Complexity.

[[Category:Algorithmic information theory|*]]

[[zh:算法信息论]]