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