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