论文标题
扩展Chaitin的不完整定理
Extending Chaitin's Incompleteness Theorem
论文作者
论文摘要
Chaitin的不完整定理指出，足够丰富的正式系统无法证明Kolmogorov复杂性的下限。在本文中，我们通过展示证明大量（但有限的）字符串数量的kolmogorov复杂性的理论来扩展该定理。这是通过首先显示此类理论具有大量信息的情况来完成的。然后，通过应用独立性假设，这种理论在物理世界中被证明是无法访问的。
Chaitin's incompleteness theorem states that sufficiently rich formal systems cannot prove lower bounds on Kolmogorov complexity. In this paper we extend this theorem by showing theories that prove the Kolmogorov complexity of a large (but finite) number of strings are inaccessible. This is done by first showing such theories have large information with the halting sequence. Then, by applying the independence postulate, such theories are shown to be inaccessible in the physical world.
