paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On the incomputability of computable dimension

论可计算维数的不可计算性
LMCS vol.Volume 16, Issue 22020匹配度 0/10 · 该论文属于可计算性理论与算法随机性，讨论康托尔空间中子集维数的不可计算性，与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等方向没有直接关联。引用 1 inbox
Ludwig Staiger
逻辑与自动机
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话：通过迭代树构造证明，康托尔空间中简单可计算子集的豪斯多夫维数、构造性维数和可计算维数都可能不可计算。

论文研究康托尔空间中可计算子集的维数可计算性问题。对于算法信息论与有效分形几何中的豪斯多夫维数、构造性维数和可计算维数，通常希望简单集合的维数能被算法求出。作者采用迭代树构造方法，构造出简单的可计算子集，使得这些维数不再是可计算的。结果表明，即使集合本身具有很低的描述复杂度，其豪斯多夫维数、构造性维数与可计算维数仍可能不可计算，从而揭示了可计算维数概念的内在不可计算性。该结论为有效维数理论中不同维数概念的算法性质提供了反例与边界。

问题
研究康托尔空间中简单可计算子集的豪斯多夫维数、构造性维数与可计算维数是否可计算。
方法
使用迭代树构造，构造简单的可计算子集作为反例。
评估
通过构造性证明展示在康托尔空间中对简单可计算子集，这些维数可能不可计算。
原文摘要（Abstract）

Using an iterative tree construction we show that for simple computable subsets of the Cantor space Hausdorff, constructive and computable dimensions might be incomputable.

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@article{Staiger20,
  title = {On the incomputability of computable dimension},
  author = {Ludwig Staiger},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 2},
  year = {2020},
  doi = {10.23638/lmcs-16(2:5)2020}
}