可计算性理论

来自计算思维百科
跳转至: 导航搜索

可计算性理论(Computability Theory)是研究计算的一般性质的数学理论。

基本概念

可计算性理论(Computability Theory)是研究计算的一般性质的数学理论。可计算理论的中心课题就是将算法这一直观概念精确化,建立计算的数学模型,研究哪些是可计算的,哪些是不可计算的,以此揭示计算的实质。由于计算与算法联系在一起,因此,可计算性理论也称算法理论。

发展

可计算理论起源于对数学基础问题的研究。从20世纪30年代开始,为了讨论所有问题是否都有求解的算法,数学家和逻辑学家从不同角度提出了几种不同的算法精确化定义。为了简洁起见,许多数学家都开始于对自然数论域中的数论函数的可计算性进行研究,提出了几种可计算函数定义。

A.Church于1935年提出了λ-转换演算,K.Godel、J.Herbrand和S.C.Kleene于1936年定义了递归函数,A.Turing和E.Post分别于1936年和1943年提出了各自的抽象计算机模型,A.A.Mapkob于1951年定义了正规算法,J.C.Shepherdson于1963年定义无限寄存器机器,50年代末和60年代初,胡世华和J.Mccarthy等人各自独立地提出了定义在字符串上的递归函数,等等。后来陆续证明,上述这些不同计算模型的计算能力都是一样的,它们所刻画的函数类均相同,即它们是等价的。

定义和特性

所谓可计算性其实应该算是一个哲学定义。通俗的说如果存在一个机械的过程,对给定的一个输入,能在有限步内给出答案,那么这个问题就是可计算性的。计算科学给可计算性的定义是:凡可用某种程序设计语言描述的问题都是可计算性问题。

图灵通过精确地描述给出了“可计算性”的形式定义,他提出一类直观而合理的抽象机,这种抽象机就是现在的图灵机。所谓可计算性是:通常能够称作算法的过程,恰好可以在图灵机上执行的过程。图灵之所以能取得成功,很重要的一条是他采用了算法思维来研究计算的过程,由此揭示可计算性概念。由于算法思维与当今在计算机上运行的程序之间有着密切的关系,从而使他的理论受到重视并广泛使用。

可计算性的特性主要有:

① 确定性。由相同的初始条件,得到相同的结果。

② 能在有限时间内,在有限设备上执行。

③ 每一个计算过程的执行都是“机械的”或“构造的”,且可以被精确地描述,使得一个设备能够接受这种描述,并用它实施该计算过程而得出同样的结果。

④ 这些计算过程可以用数学术语编写,它们含有能够由自然数表示的对象,同时总能将这种计算过程中的运算解释为算术运算,所得到的数值结果就是在应用中可能采取的值,进一步说,这些计算过程的语句甚至也是有限的,且自身能被表示为自然数。

主要内容

意义

可计算性理论的基本思想、概念和方法,被广泛应用于计算科学的各个领域。建立数学模型的方法在计算科学中被广泛采用。递归的思想被用于程序设计,产生了递归过程的数据结构,也影响了计算机体系结构。λ演算被用于研究程序设计语言的语义,例如,表处理语言就以λ演算为理论基础。

递归函数论的建立对于数学基础的研究具有十分重要的作用。数学家希尔伯特曾希望将整个数学形式化,建立了一个协调、完备的大系统。哥德尔不完全性定理表明,这种形式系统不可能是完备的。为了证明不完全性定理,K.Godel发明了原始递归函数。K.Godel定理对数学具有重要的影响,对认识论乃至整个哲学也有深刻的意义。

计算学科的一个基本结论是不可计算的函数要比可计算的函数多得多。特别地,虽然许多问题是可判定的,但更多的问题是不可判定的,例如,停机问题和波斯特对应问题都是不可判定的。