使用相对化随机的方法探讨随机性的可定义性

In this project, we investigate on definability of a randomness notion via another with relativization. To compare two randomness notions with each other, we ask whether a given randomness notion can be defined via another randomness notion. We formalize our question using the concept of relativization of randomness. We will focus on two parts, at first we given some solutions to our formalized questions which relative to the Schorr randomness. Secondly, an even older question in algorithmic randomness is that of establishing the relationship between Kolmogorov-Loveland randomness and Martin-Lof randomness. In this project, we will study this open question and give the part or total answer.

本项目通过使用相对化随机性的方法，研究如何定义随机性，从而达到研究随机性本身的目的。本项目拟通过回答问题的方式，研究方法主要利用低度（Lowness）与高度（Highness）的相关性质，研究几种常见随机性概念之间的关系。研究内容主要包括两大部分，首先研究Scnorr随机性与Martin-Lof随机性之间的等价关系，即使用可计算集合做为Martin-Lof随机性的谕示，讨论如何定义Schorr随机性，从而达到研究Schorr随机性的本身的性质。其次重点解决算法随机性里最热点的未解问题，即Kolmogorov-Loveland随机性与Martin-Lof随机性是否等价？本项目将使用弱化Kolmogorov-Loveland随机性的方法，希望对这一未解问题给出部分或全部回答。

本项目通过使用相对化随机性的方法，研究如何定义随机性，从而达到研究随机性本身的目的。 研究方法主要利用低度(Lowness)与高度(Highness)的相关性质 ，研究几种常见随机性概念之间的关系。研究内容主要包括两大部分，在算法随机性方面，我们证明了0-Schnorr随机性等价于是Martin-Lof随机性相对于Low集合与ML集合。顺利按预期完成了目标。其次重点解决KL随机性与ML随机性是否等价的问题，我们证明了KL随机性强于单身随机性，但是不等价于自同态随机性。此问题是对未解问题的部分回答。. 在算法复杂度方面，将一致二分叉树上的的结果推广到均衡多分叉树上，证明了当树的跟为零的概率介于(0,1)时，Eigen-分布是独立同分布（IID）。此结果是对Suzuki-Niida提出的未解问题给于了解答。

内容获取失败，请点击重试