图灵机在康托集上的可计算性

Computability of Turing Machine on Cantor Sets

对定义在集合∑*上的函数f:■(∑*)n→∑*引入可计算性,该方法不能应用于不可数集合M,如实数集R。利用无限符号序列作为名,同时定义作用于这些无限序列函数的可计算性,将可计算性拓展到以上不可数集合,从而引入型2图灵机。部分可递归函数(即可计算数函数)集合P(1)中的概念"有效的哥德尔数"φ:N→P(1)是一般递归理论的基础,而由通用图灵机定理等价唯一定义。利用∑ω将φ的概念推广到可计算函数和f:■(∑a)n→∑b某些连续函数f:■(∑a)→∑b,其中a,b∈〔ω,*〕,这就是型2图灵机的表示。

In view of computability for functions f：lohtain in （∑^＊）^n→∑^＊ on the set ∑^＊ , this method cannot be applied for introducing computability on uncountable sets M like the set R of real numbers. The above concepts will be extended to uncountable set by using infinite sequences of symbols of names and by defining computability for functions which transform such infinite sequences with Type-2 machine. In recursion theory the concept of an ＂effective Godel numbering＂ φ：N→P^（1） is fundamental. This number φ is defined uniquely up to equivalence by the universal turning machine theorem. We generalize the number φ to notations of the computable functions f：lohtain in ∑^a^n→∑^b by means of ∑^ω and the representations of certain continuous functions f：lohtain in ∑^a^n→∑^b, where a, b ∈ {ω,＊ }. This is the presentation and notation of Type-2 machine.