Computability and Probability

这个项目的主要部分是研究概率在可计算性理论和算法随机性中的应用。首席研究员已经表明，随机数发生器操作中的有限错误可能导致无法使用算法补偿的随机性损失。一个主要的目标是确定在任何时候，真正的随机性是否可以随着这些错误的数量变小而重建。利用概率势理论和随机闭集对已有结果进行了证明。这种方法与其他研究人员的工作相结合，导致了更丰富的图像的可能概念的随机性分数有效豪斯多夫维数，并打开了问题的链接与算法信息理论的物理机械解释。该项目的次要但也是不可分割的一部分是概率的可计算性理论分析。该项目的目的是从可计算性理论的角度进一步理解随机对象，并帮助澄清随机数生成的理论局限性，这是一个在科学和工程领域有广泛应用的领域。特别是，目的是了解在多大程度上可以修复受损的随机性源，或证明这种修复是不可能的。其目标不一定是重建原始的未损坏的随机数据，但获得一些随机数据。使用图灵可计算性理论可以使特定数据是随机的这一概念变得精确。这个想法是，如果没有计算机算法可以检测到其中的任何模式，那么0和1的序列对于所有实际目的来说都是随机的。由于艾伦·图灵和其他人的工作，这个想法可以被抽象地研究，而不必担心特定的物理计算机和实现。相反，算法的理论研究在现代计算机的发展中发挥了重要作用。图灵可计算性已经在数学的许多领域中使用，以表明某些任务不能由任何算法执行。例如，Matiyasevich表明，这是为任务找到一个整数根的多项式方程。将这种可计算性理论应用于概率和随机性是特别富有成效的。概率论预测实验的结果会有什么性质，而不一定给出任何合理的具体例子。随机？结果。例如，在飞镖板上投掷飞镖的实验可能会导致板上的任何区域被击中，但永远不会导致完美的靶心或板上的任何其他预定义点。从理论上讲，总会有一个小的误差，也许是肉眼看不到的;这可以通过说实验的结果是飞镖板上的算法随机点来表达。人们还可以研究一系列观测的算法随机性如何，以便科学方法通过统计方法产生关于观测现象的信息。数学描述的直观概念的一个单独的随机对象作为一个没有可计算的或可定义的不太可能的属性可能有助于更好地欣赏概率和随机性的科学家以及公众。

The primary part of this project is an investigation of applications of probability to computability theory and algorithmic randomness. The principal investigator has shown that a limited amount of errors in the operation of a random number generator can lead to a loss of randomness that cannot be compensated for using algorithms. A main goal is to determine if at any point true randomness can be reconstructed as the amount of such errors becomes small. The results already obtained were proved using probabilistic potential theory and random closed sets. This approach in conjunction with work by other researchers has lead to a richer picture of the possible notions of randomness for fractional effective Hausdorff dimension, and opened up questions about a link with a statistical-mechanical interpretation of algorithmic information theory. A secondary but also integral part of the project is the computability-theoretic analysis of probability. An example here is the determination of the Kolmogorov complexity of finite strings describing random walks that approximate Brownian motion.The project aims to further the understanding of random objects in computability-theoretic terms, and help clarify the theoretical limitations of random number generation, a field of wide application in science and engineering. In particular, the aim is to understand to what extent one can repair damaged randomness sources, or prove that such a repair is impossible. The goal is not necessarily to reconstruct the original undamaged random data but to obtain some random data. The notion of particular data being random can be made precise using the theory of Turing computability. The idea is that a sequence of 0s and 1s is random for all practical purposes if no computer algorithm can detect any pattern in it. Thanks to the work of Alan Turing and others, this idea can be studied abstractly without worrying about particular physical computers and implementations. Conversely, the theoretical study of algorithms played a large role in the development of modern computers. Turing computability has been used in many areas of mathematics to show that certain tasks cannot be carried out by any algorithm. For example, Matiyasevich showed this for the task of finding an integer root of a polynomial equation. Applying this computability theory to probability and randomness is especially fruitful. The theory of probability predicts what properties the outcome of an experiment will have, without necessarily giving any specific example of a reasonable ?random? outcome. For instance, the experiment of throwing a dart at a dart board can result in any region of the board being hit, but will never result in a perfect bulls-eye or any other predefined point on the board. In theory there will always be a small error, perhaps invisible to the naked eye; this can be expressed by saying that the result of the experiment is an algorithmically random point on the dart board. One can also study how algorithmically random a sequence of observations must be for the scientific method to yield information about the phenomenon underlying the observations via the methods of statistics. The mathematical delineation of the intuitive notion of an individual random object as one having no computable or definable unlikely properties may contribute to a better appreciation of probability and randomness by scientists as well as the general public.