Editing Kolmogorov complexity (section)

==Kolmogorov randomness==
{{See also|Algorithmically random sequence}}
''Kolmogorov randomness'' defines a string (usually of [[bit]]s) as being [[randomness|random]] if and only if every [[computer program]] that can produce that string is at least as long as the string itself.  To make this precise, a universal computer (or [[universal Turing machine]]) must be specified, so that "program" means a program for this universal machine. A random string in this sense is "incompressible" in that it is impossible to "compress" the string into a program that is shorter than the string itself. For every universal computer, there is at least one algorithmically random string of each length.<ref>There are 2<sup>''n''</sup> bit strings of length ''n'' but only 2<sup>''n''</sup>-1 shorter bit strings, hence at most that much compression results.</ref>  Whether a particular string is random, however, depends on the specific universal computer that is chosen. This is because a universal computer can have a particular string hard-coded in itself, and a program running on this universal computer can then simply refer to this hard-coded string using a short sequence of bits (i.e. much shorter than the string itself).

This definition can be extended to define a notion of randomness for ''infinite'' sequences from a finite alphabet. These [[algorithmically random sequence]]s can be defined in three equivalent ways. One way uses an effective analogue of [[measure theory]]; another uses effective [[Martingale (probability theory)|martingales]].  The third way defines an infinite sequence to be random if the prefix-free Kolmogorov complexity of its initial segments grows quickly enough&nbsp;— there must be a constant ''c'' such that the complexity of an initial segment of length ''n'' is always at least ''n''−''c''.  This definition, unlike the definition of randomness for a finite string, is not affected by which universal machine is used to define prefix-free Kolmogorov complexity.<ref>{{cite journal |doi=10.1016/s0019-9958(66)80018-9 |title=The definition of random sequences |journal=Information and Control |volume=9 |issue=6 |pages=602–619 |year=1966 |last=Martin-Löf |first=Per |doi-access=free }}</ref>