族谱网 头条 人物百科

递归论

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

概述:计算的概念

递归论所考虑的基本问题是,给定一个从自然数到自然数的函数f,f是否是可以被计算的。“可以被计算”,我们先将其当作一个直观的概念。根据直觉,人们一般会认为,一个函数可以被计算是存在一个给定的过程,接受一个自然数n后,该过程进行一定的操作并给出f(n)作为输出。将计算这一直观的概念上升到数学层面的形式化定义这一工作是递归论的根本,并由哥德尔、邱奇、图灵、克莱尼和Emil Post等人在1930年代奠定。他们将图灵可计算性作为有效计算的形式化。

在递归论的基本概念被给定之后,一方面人们将该观念应用于数学中,从而证明了一系列自然的问题,如字问题,以及希尔伯特第十问题等问题是不可计算的。另一方面,理论家们进一步拓展,开始了相对可计算性,图灵度等问题的研究。如今,递归论仍是数理逻辑中活跃的领域。

历史

递归论理论起源自哥德尔、邱奇、图灵、克莱尼和Emil Post在1930年代的工作。他们获得的基本结果建立了图灵可计算性作为有效计算的非正式想法的正确的形式化。通过能行计算的严格定义带来了在数学中有些问题是不可有效判定的最初证明。邱奇和图灵独立的证明了停机问题不能进行判定,而Post证明了在Thue系统中确定一个字符串是否有规范形式(类似于在λ演算中一个项是否有规则形式)不能有效的确定。

不可解度结构的研究,包括图灵度、多一度和类似的结构,是这个领域的重要部分。图灵度的研究发起自Kleene和Post [1954]。大量的可计算性理论中的研究已经投入到图灵度的性质的研究中。开始于1970年代,图灵度的研究焦点已经从局部结构性质转移到全局性质,比如图灵度的自同构(automorphism)和0′{\displaystyle 0"}的可定义性。

在1930年代确定了最初的例子之后,很多数学问题已经被证实是不可判定的。Novikov和Boone在1950年代证实,给出在一个有限出现群中的一个字,没有有效的过程来判定这个字所表示的元素是否是这个群的单位元素。这个结果被用来证实很多其他问题是不可判定的,比如两个有限单形(simplicial complex)是否表现同胚空间的问题。在1970年,尤里·马季亚谢维奇对希尔伯特第十问题给出了否定答案,它提问是否有有效的过程来判定有有限多个有理数上的变量的丢番图方程是否有在有理数上的解。这个否定解答是对Martin Davis、Hilary Putnam和Julia Robinson在1961年给出的部分解答的巩固。

递归论包括可计算性的一般概念的研究,比如超算术可归约性(hyperarithmetic degrees)、α-递归论和可构成度(constructibility degrees)。

链接

μ算子

图灵度

多一归约

枚举归约

超算术理论

算术层次

分析层次

能行描述集合论

图灵机

引用

S. Barry Cooper, Computability Theory, Chapman & Hall/CRC, ISBN 1-58488-237-9(textbook)

Nigel J. Cutland, Computability, An introduction to recursive function theory, Cambridge University Press, ISBN 0-521-29465-7 (paperback), 1980.

Herbert B. Enderton [1977] : Elements of Recursion Theory, in : Jon Barwise, ed., Handbook of Mathematical Logic, pp. 527-566.

S. C. Kleene and E. L. Post [1954], The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59, 379--407.

Piergiorgio Odifreddi, Classical Recursion Theory, North-Holland, ISBN 0-444-87295-7(textbook)

Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1(textbook)

R. I. Soare, Computability and recursion, Bull. Symbolic Logic 2 (1996) 284-- 321.

Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7(textbook)


免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。

——— 没有了 ———
编辑:阿族小谱
发表评论
写好了,提交
{{item.label}}
{{commentTotal}}条评论
{{item.userName}}
发布时间:{{item.time}}
{{item.content}}
回复
举报
点击加载更多
打赏作者
“感谢您的打赏,我会更努力的创作”
— 请选择您要打赏的金额 —
{{item.label}}
{{item.label}}
打赏成功!
“感谢您的打赏,我会更努力的创作”
返回

更多文章

更多精彩文章
打赏
私信

推荐阅读

· 递归
递归程序在支持自调用的编程语言中,递归可以通过简单的函数调用来完成,如计算阶乘的程序在数学上可以定义为:这一程序在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...
· 递归
语言例子从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?“从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?‘从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?……’”一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到:“一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到:‘一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到……’”正式定义在数学和计算机科学中,递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他...
· 递归语言
定义递归语言有两种等价的主要定义:递归语言是在形式语言的字母表上的所有可能的字的集合的递归子集。设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\,}图灵可判定语言与图灵...
· 递归可枚举语言
形式定义递归可枚举语言定义:设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...
· 原始递归函数
定义原始递归函数接受自然数或自然数的元组作为参数并生成自然数。接受n个参数的函数叫做n-元函数。基本原始递归函数用如下公理给出:常数函数:0元常数函数0是原始递归的。后继函数:1元后继函数S,它接受一个参数并返回皮亚诺公理给出的后继数,是原始递归的。投影函数:对于所有n≥1和每个1≤i≤n的i,n元投影函数Pi,它接受n个参数并返回它们中的第i个参数,是原始递归的。更加复杂的递归函数可以通过应用下列公理给出的运算来获得:复合:给定k元原始递归函数f,和k个m元原始递归函数g1,...,gk,f和g1,...,gk的复合,也就是m元函数h(x1,...,xm)=f(g1(x1,...,xm),...,gk(x1,...,xm)),是原始递归的。原始递归:给定k元原始递归函数f,和k+2元原始递归函数g,定义为f和g的原始递归的k+1元函数,也就是函数h这里的h(0,x1,...,xk)=f(...

关于我们

关注族谱网 微信公众号,每日及时查看相关推荐,订阅互动等。

APP下载

下载族谱APP 微信公众号,每日及时查看
扫一扫添加客服微信