递归

形式定义递归可枚举语言定义：设S⊆Σ为一个语言，E是一个枚举器，若L（E）=S，则称E枚举了语言S。若存在这样的E，S就称为递归可枚举语言。注意，枚举器E可以以任意的顺序枚举语言L（E），而且L（E）中的某个串可能会被E多次重复地打印。图灵可识别语言定义：设M{\displaystyleM}是一台图灵机，若在输入串ωω-->{\displaystyle\omega}上M{\displaystyleM}运行后可进入接受状态并停机，则称M{\displaystyleM}接受串ωω-->{\displaystyle\omega}。M{\displaystyleM}所接受的所有字符串的集合称为M{\displaystyleM}所识别的语言，简称M{\displaystyleM}的语言，记作L(M){\displaystyleL(M)}。设S⊆⊆-->ΣΣ-->∗∗-->{\displaystyle...

定义递归语言有两种等价的主要定义:递归语言是在形式语言的字母表上的所有可能的字的集合的递归子集。设S⊆Σ是一个语言，M是一台图灵机，若对于任何字符串ω∈Σ，有ω∈S当且仅当M接受ωω∉S当且仅当M拒绝ω则称M判定语言S。若存在这样的M，S就称为图灵可判定语言。闭包性质递归语言是在下列运算下是闭合的。就是说，如果L和P是两个递归语言，则下列语言也是递归的:L的Kleene星号L∗∗-->{\displaystyleL^{*}}L的非删除(non-erasing)同态φ(L)L和P的串接L∘∘-->P{\displaystyleL\circP}并集L∪∪-->P{\displaystyleL\cupP}交集L∩∩-->P{\displaystyleL\capP}L的补集LC{\displaystyleL^{C}\,}差集L−−-->P{\displaystyleL-P\,}图灵可判定语言与图灵...

递归程序在支持自调用的编程语言中，递归可以通过简单的函数调用来完成，如计算阶乘的程序在数学上可以定义为：这一程序在Scheme语言中可以写作：(define(factorialn)(if(=n0)1(*n(factorial(-n1)))))不动点组合子即使一个编程语言不支持自调用，如果在这语言中函数是第一类对象（即可以在运行期创建并作为变量处理），递归可以通过不动点组合子（英语：Fixed-pointcombinator）来产生。以下Scheme程序没有用到自调用，但是利用了一个叫做Z算子（英语：Zcombinator）的不动点组合子，因此同样能达到递归的目的。(defineZ(lambda(f)((lambda(recur)(f(lambdaarg(apply(recurrecur)arg))))(lambda(recur)(f(lambdaarg(apply(recurrecur)a...

概述：计算的概念递归论所考虑的基本问题是，给定一个从自然数到自然数的函数f，f是否是可以被计算的。“可以被计算”，我们先将其当作一个直观的概念。根据直觉，人们一般会认为，一个函数可以被计算是存在一个给定的过程，接受一个自然数n后，该过程进行一定的操作并给出f(n)作为输出。将计算这一直观的概念上升到数学层面的形式化定义这一工作是递归论的根本，并由哥德尔、邱奇、图灵、克莱尼和EmilPost等人在1930年代奠定。他们将图灵可计算性作为有效计算的形式化。在递归论的基本概念被给定之后，一方面人们将该观念应用于数学中，从而证明了一系列自然的问题，如字问题，以及希尔伯特第十问题等问题是不可计算的。另一方面，理论家们进一步拓展，开始了相对可计算性，图灵度等问题的研究。如今，递归论仍是数理逻辑中活跃的领域。历史递归论理论起源自哥德尔、邱奇、图灵、克莱尼和EmilPost在1930年代的工作。他们获得的...

语言例子从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓志铭，让未来的狗可以看到：“一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓志铭，让未来的狗可以看到：‘一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓志铭，让未来的狗可以看到……’”正式定义在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他...