Computability and Probability

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

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.