一句话：揭示图灵跳跃与极限可计算之间的伴随关系，并在表示空间上建立形式化 Galois 连接。
论文研究极限可计算函数与图灵跳跃、相对停机问题可计算性之间的关系。作者将输入侧图灵跳跃与输出侧取极限视为一对伴随操作，构造其单子，刻画 low 函数及相对停机问题可计算函数；这两类是能与极限可计算函数前后复合仍保持该类的最大函数类。作者在表示空间格上建立形式化 Galois 连接，并给出可计算度量空间版本。关键结果：点与序列上两类可计算性一致，但连续函数上极限可计算严格更大；在可计算度量空间上，相对停机可计算等价于极限可计算且连续模相对停机可计算。由此推出极限可计算的 Lipschitz 函数自动相对停机可计算；1-泛型点作为规范连续点，限制到这些点时两类一致，并应用于可计算分析。
Limit computable functions can be characterized by Turing jumps on the input side or limits on the output side. As a monad of this pair of adjoint operations we obtain a problem that characterizes the low functions and dually to this another problem that characterizes the functions that are computable relative to the halting problem. Correspondingly, these two classes are the largest classes of functions that can be pre or post composed to limit computable functions without leaving the class of limit computable functions. We transfer these observations to the lattice of represented spaces where it leads to a formal Galois connection. We also formulate a version of this result for computable metric spaces. Limit computability and computability relative to the halting problem are notions that coincide for points and sequences, but even restricted to continuous functions the former class is strictly larger than the latter. On computable metric spaces we can characterize the functions that are computable relative to the halting problem as those functions that are limit computable with a modulus of continuity that is computable relative to the halting problem. As a consequence of this result we obtain, for instance, that Lipschitz continuous functions that are limit computable are automatically computable relative to the halting problem. We also discuss 1-generic points as the canonical points of continuity of limit computable functions, and we prove that restricted to these points limit computable functions are computable relative to the halting problem. Finally, we demonstrate how these results can be applied in computable analysis.
@article{paperbot383,
title = {A Galois connection between Turing jumps and limits},
author = {Vasco Brattka},
journal = {Logical Methods in Computer Science},
volume = {Volume 14, Issue 3},
number = {Computability and logic},
year = {2018},
doi = {10.23638/lmcs-14(3:13)2018}
}