paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Weihrauch-completeness for layerwise computability

分层可计算性的 Weihrauch 完备性
LMCS vol.Volume 14, Issue 22018匹配度 1/10 · 该论文属于可计算性理论与算法随机性中的 Weihrauch 归约/分层可计算性研究,与用户关注的 PL/AI 静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等方向没有直接关联。虽然涉及形式化理论,但并非面向程序分析、验证工具或工业落地场景。引用 10 inbox
Arno Pauly, Willem Fouché, George Davie
crossref: 2026-09-10

AI 速览

一句话:提出分层可计算性框架下的 Weihrauch 完备性概念,并给出若干自然实例及命中时间算子的反例。

本文研究 Weihrauch 归约与分层可计算性之间的关系。作者提出“对于分层可计算性而言的 Weihrauch 完备性”这一概念,并围绕复杂振荡、重对数律和 Birkhoff 遍历定理构造若干自然例子,说明这些对象在该意义下具有完备性。进一步地,论文考察命中时间算子,发现它们虽然与前例具有相同的 Weihrauch 度,却不具备分层可计算性。这一结果说明,相同的 Weihrauch 度并不足以决定分层可计算性,从而揭示了两种可计算性度量之间的精细区别,并为比较此类分析构造的可计算强度提供了新工具。

问题
如何在 Weihrauch 归约框架下刻画分层可计算对象的完备性,以及同一 Weihrauch 度是否能决定分层可计算性。
方法
定义分层可计算性的 Weihrauch 完备性,并分析复杂振荡、重对数律、Birkhoff 定理相关实例以及命中时间算子。
评估
通过构造并比较这些自然实例的 Weihrauch 度与分层可计算性,特别是给出具有相同 Weihrauch 度但非分层可计算的命中时间算子。
原文摘要(Abstract)

We introduce the notion of being Weihrauch-complete for layerwise computability and provide several natural examples related to complex oscillations, the law of the iterated logarithm and Birkhoff's theorem. We also consider hitting time operators, which share the Weihrauch degree of the former examples but fail to be layerwise computable.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot403,
  title = {Weihrauch-completeness for layerwise computability},
  author = {Arno Pauly and Willem Fouché and George Davie},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 14, Issue 2},
  year = {2018},
  doi = {10.23638/lmcs-14(2:11)2018}
}