Computing and Information Technology Interactive Digital Educational Library

 

CITIDEL >
Planet Math Computer Science  >
Planet Math Computer Science Collection >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10117/1272

Title: Kolmogorov complexity
Issue Date: 2-Jan-2005
Publisher: PlanetMath
Citation: http://planetmath.org/encyclopedia/KolmogorovComplexity.html
Abstract: Consider flipping a coin 50 times to obtain the binary string 000101000001010100010000010101000100000001010000010. Can we call this random? The string has rather an abundance of 0s, and on closer inspection every other bit is 0. We wouldn't expect even a biased coin to come up with such a pattern. Still, this string has probability ... , just like any other binary string of the same length, so how can we call it any less random? ... Kolmogorov Complexity provides an answer to these questions in the form of a measure of information content in individual objects. Objects with low information content may be considered non-random. The topic was founded in the 1960s independently by three people: Ray Solomonoff, Andrei Kolmogorov, and Gregory Chaitin. See Kolmogorov complexity function and invariance theorem for more details.
URI: http://www.citidel.org/handle/10117/1272
Appears in Collections:Planet Math Computer Science Collection

Files in This Item:

File SizeFormat
KolmogorovComplexity.html17KbHTMLView/Open

All items in DSpace are protected by copyright, with all rights reserved.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2006 MIT and Hewlett-Packard - Feedback