论文标题
连续，换能器和常规功能的可计算分类
Computable classifications of continuous, transducer, and regular functions
论文作者
论文摘要
我们开发了一种系统的算法框架，该框架使用索引集将全球和本地分类问题团结起来。我们证明，连续（二进制）常规函数的分类问题几乎在线性中，线性时lipschitz函数为$σ^0_2 $ -complete。 （每个常规函数都是点式线性时间lipschitz。）我们证明$ f \ colon [0,1] \ rightArrow \ mathbb {r} $ is（binary）trandducer当它连续常规时。作为许多后果之一，我们的$σ^0_2 $ - 复杂性结果也涵盖了换能器函数的类。最后，我们证明了Banach Space $ c [0,1] $实价连续功能承认可分离的Banach空间之间的算术分类。我们的证明结合了抽象可计算理论，自动机理论和功能分析的方法。
We develop a systematic algorithmic framework that unites global and local classification problems using index sets. We prove that the classification problem for continuous (binary) regular functions among almost everywhere linear, pointwise linear-time Lipschitz functions is $Σ^0_2$-complete. (Every regular function is pointwise linear-time Lipschitz.) We show that a function $f\colon [0,1] \rightarrow \mathbb{R}$ is (binary) transducer if and only if it is continuous regular. As one of many consequences, our $Σ^0_2$-completeness result covers the class of transducer functions as well. Finally, we show that the Banach space $C[0,1]$ of real-valued continuous functions admits an arithmetical classification among separable Banach spaces. Our proofs combine methods of abstract computability theory, automata theory, and functional analysis.
