论文标题
计算的递归理论基础
A recursion theoretic foundation of computation over real numbers
论文作者
论文摘要
我们使用类似于Gödel和Kleene定义的原始和部分递归函数类似的功能方案来定义一类可计算函数。我们表明，这类功能也可以由主奴隶机器（像设备一样的图灵机器）进行表征。表征的证据以kleene的风格给出了正常形式的定理。此外，这种表征是两种最具影响力的计算理论，即实数的自然组合，即效果型型理论（TTE）（例如，参见Weihrauch）和Blum-Shub-smale computitation（BSS）。在这一可计算性概念下，实数的递归（或可计算）子集完全有效$δ^0_2 $集。
We define a class of computable functions over real numbers using functional schemes similar to the class of primitive and partial recursive functions defined by Gödel and Kleene. We show that this class of functions can also be characterized by master-slave machines, which are Turing machine like devices. The proof of the characterization gives a normal form theorem in the style of Kleene. Furthermore, this characterization is a natural combination of two most influential theories of computation over real numbers, namely, the type-two theory of effectivity (TTE) (see, for example, Weihrauch) and the Blum-Shub-Smale model of computation (BSS). Under this notion of computability, the recursive (or computable) subsets of real numbers are exactly effective $Δ^0_2$ sets.
