“Chaitin 的停机概率给出一个可从下逼近却不可计算的随机实数,其真前缀能够解决相应有限停机问题。有效 Hausdorff 维数则把所有前缀的统一常数亏损放宽为渐近信息密度;维数一仍可能被…”
形式陈述
在 Cantor 空间,函数
下半可计算指存在统一全可计算的有理近似
其中
直觉
维数问:在无限多个长前缀上,每一位至少需要多少不可压缩信息。下极限让低信息密度的长阶段起决定作用;偶尔出现一大块复杂数据,未必提高这个下极限。
当
例子与边界
每个随机位后插入一个零
令
反过来,从
这个例子不是把随机性一分为二:
维数一仍可有可计算异常
在位置
结合一般上界,信息密度趋一。但要求前
刻画定理的编码机制
先设
柱集分裂等式使它成为下半可计算的
反过来,设下半可计算
对每个
选择一个足够大的固定整数
推论与应用
$K$-平凡序列和所有可计算序列维数均为零,但零维数不等于可计算。用越来越稀疏的位置保存不可计算数据,仍可能保留全部图灵信息而令密度归零。
若将 liminf 换为 limsup,得到的是有效强维数(与有效 packing 维数对应),衡量高信息密度阶段;不能只换一个极限符号而沿用同一个名称。
参考资料
- [1] Elvira Mayordomo, A Kolmogorov Complexity Characterization of Constructive Hausdorff Dimension, 2002,Theorem 3.1、Corollary 3.2 及短证明;正式发表于 Information Processing Letters 84, pp. 1–3。
- [2] Ludwig Staiger, Constructive Dimension Equals Kolmogorov Complexity, CDMTCS-210,2003,修订于 2004 年 11 月,§§2–3:树半测度、Lemma 2 与 Theorem 5。