更改

===Kolmogorov complexity===

===Kolmogorov complexity===

{{Main|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.

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.

柯氏复杂性和算法随机性领域是在20世纪60年代和70年代由 Chaitin，Kolmogorov，Levin，martin-l ö f 和 Solomonoff 发展起来的(这些名字在《字母顺序给出; 大部分研究是独立的，当时并不理解随机性概念的统一性)。其主要思想是考虑一个通用图灵机 u，并用最短输入 p 的长度来度量一个数字(或字符串) x 的复杂度，这样 u (p)就可以输出 x。这种方法通过引用有限对象的随机性概念，彻底改变了早期确定无限序列(等价地，自然数子集的特征函数)是否是随机的方法。柯氏复杂性不仅成为一个独立的研究对象，而且也被应用到其他学科，作为获得证据的工具。

'''<font color="#ff8000">柯尔莫哥洛夫复杂性 Kolmogorov complexity</font>'''和'''<font color="#ff8000">算法随机性 algorithmic randomness</font>'''领域是在20世纪60年代和70年代由蔡廷，柯尔莫哥洛夫，莱文，马丁洛夫和 索罗门诺芙发展起来的(这些名字是按字母顺序列出的;许多研究都是独立进行的，而且当时人们并不理解随机性概念的统一性)。其主要思想是考虑一个'''<font color="#ff8000">通用图灵机 universal Turing machine</font>''' u，并用最短输入 p 的长度来度量一个数字(或字符串) x 的复杂度，这样 u (p)就可以输出 x。这种方法通过引用有限对象的随机性概念，彻底改变了早期确定无限序列(等价地，自然数子集的特征函数)是否是随机的方法。柯尔莫哥洛夫复杂性不仅成为一个独立的研究对象，而且也被应用到其他学科，作为获得证据的工具。

There are still many open problems in this area. For that reason, a recent research conference in this area was held in January 2007<ref>[http://www-2.dc.uba.ar/logic2007/ Conference on Logic, Computability and Randomness] {{Webarchive|url=https://web.archive.org/web/20071226220454/http://www-2.dc.uba.ar/logic2007/ |date=2007-12-26 }}, January 10–13, 2007.</ref> and a list of open problems<ref>[http://www.cs.auckland.ac.nz/~nies/ The homepage] of Andre Nies has a list of open problems in Kolmogorov complexity</ref> is maintained by Joseph Miller and Andre Nies.

There are still many open problems in this area. For that reason, a recent research conference in this area was held in January 2007<ref>[http://www-2.dc.uba.ar/logic2007/ Conference on Logic, Computability and Randomness] {{Webarchive|url=https://web.archive.org/web/20071226220454/http://www-2.dc.uba.ar/logic2007/ |date=2007-12-26 }}, January 10–13, 2007.</ref> and a list of open problems<ref>[http://www.cs.auckland.ac.nz/~nies/ The homepage] of Andre Nies has a list of open problems in Kolmogorov complexity</ref> is maintained by Joseph Miller and Andre Nies.

There are still many open problems in this area. For that reason, a recent research conference in this area was held in January 2007 and a list of open problems is maintained by Joseph Miller and Andre Nies.

There are still many open problems in this area. For that reason, a recent research conference in this area was held in January 2007 and a list of open problems is maintained by Joseph Miller and Andre Nies.

 

 

===Frequency computation===

===Frequency computation===