Editing Computability theory (section)

===Kolmogorov complexity===
{{Main|Kolmogorov complexity}}

The field of [[Kolmogorov complexity]] and [[algorithmic randomness]] was developed during the 1960s and 1970s by Chaitin, Kolmogorov, Levin, Martin-Löf and Solomonoff (the names are given here in alphabetical order; much of the research was independent, and the unity of the concept of randomness was not understood at the time). The main idea is to consider a [[universal Turing machine]] ''U'' and to measure the complexity of a number (or string) ''x'' as the length of the shortest input ''p'' such that ''U''(''p'') outputs ''x''. This approach revolutionized earlier ways to determine when an infinite sequence (equivalently, characteristic function of a subset of the natural numbers) is random or not by invoking a notion of randomness for finite objects. Kolmogorov complexity became not only a subject of independent study but is also applied to other subjects as a tool for obtaining proofs.
There are still many open problems in this area.{{efn|A list of open problems is maintained by Joseph Miller and André Nies, the [http://www.cs.auckland.ac.nz/~nies/ André Nies's homepage] has it published.}}