paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On the extension of computable real functions

论可计算实函数的延拓
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 1/10 · 该论文属于可计算性理论与可计算分析,研究可计算实函数的可计算延拓与左可计算实数边界,未涉及静态分析、Agentic 程序、LLM、浮点程序分析或贝叶斯程序分析。与用户研究方向仅有极弱的形式化/可计算性关联,不构成实质匹配。引用 1 inbox
Mathieu Hoyrup, Walid Gomaa
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:研究定义在左可计算实数边界区间上的可计算实函数何时能可计算延拓,并刻画其充要条件。

本文研究定义在区间上的可计算实函数,区间边界为左可计算实数(left-c.e. real),探讨该函数能否被可计算地延拓到边界。作者从数学分析、有效拓扑与经典可计算理论之间的联系出发,给出了可计算延拓的充要条件。结果表明,延拓可能性既取决于函数在边界附近的行为,也取决于边界所属的左可计算实数类,即该实数的构造方式。特别地,论文考察了一类由 c.e. 集合的可计算枚举构造的锯齿函数(sawtooth functions),说明边界构造信息在延拓问题中的作用。

问题
对于定义在以左 c.e. 实数为端点的区间上的可计算函数,何时存在可计算延拓?
方法
结合可计算分析、有效拓扑与经典可计算性理论,分析函数在边界附近的行为以及边界左 c.e. 实数的构造类。
评估
以理论刻画为主,给出可计算延拓的充要条件,并通过由 c.e. 集可计算枚举构造的锯齿函数类展示边界构造方式的影响。
原文摘要(Abstract)

We investigate interrelationships among different notions from mathematical analysis, effective topology, and classical computability theory. Our main object of study is the class of computable functions defined over an interval with the boundary being a left-c.e. real number. We investigate necessary and sufficient conditions under which such functions can be computably extended. It turns out that this depends on the behavior of the function near the boundary as well as on the class of left-c.e. real numbers to which the boundary belongs, that is, how it can be constructed. Of particular interest a class of functions is investigated: sawtooth functions constructed from computable enumerations of c.e. sets.

链接与引用

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

BibTeX
@inproceedings{HoyrupG17,
  title = {On the extension of computable real functions},
  author = {Mathieu Hoyrup and Walid Gomaa},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005067}
}