时间：2022-10-30 14:30:02 | 来源：信息时代
时间：2022-10-30 14:30:02 来源：信息时代
可计算性理论 : 研究关于计算一般性质的数学理论,它起源于对数学基础问题的研究。在过去多少年中,人们对“数学”与“计算”这两个不同概念一直没有区分,而且都沉淀于“数学问题都能计算”的误区中,但是当数学发展到一定阶段后人们发现,“数学”与“计算”是不同概念,于是就提出了: “计算的实质是什么? ” “是否所有数学问题都可计算? ”这就出现了可计算性理论。
可计算性理论属数理逻辑中的递归论,它出现于20世纪30年代,研究计算的数学模型,是使用一种数学模型来给“计算”作精确的定义。在1936年,Godel、Herbrand和Kleene定义了递归函数;Church于1935年提出了λ换位演算;Turing于1936年定义了图灵机,其主要内容是:
(1) 图灵机是一种抽象计算机,它可以精确描述计算的特性。一台标准图灵机由三部分组成: 一条双向无限长且被分为一个个小方格的磁带、一个有限状态控制器以及一个读写磁头。机器的工作是根据控制器状态及磁头定位所在磁带方格上的信息决定的,读写磁头在磁带上打印一个符号,磁头向左或向右移动一格,机器由原有的一个状态转向另一个状态。按照此原理不断工作,直至停机。表面看来,图灵机功能简单,但是它有无限的空间(磁带方格)与时间(计算步数),因此只要有足够的时间与空间,它能处理任何一个可计算函数。
(2)λ换位演算是一种定义函数的形式演算系统,在此演算中引入了符号“λ”,以明确区分函数与函数值,并把函数值的计算归结为按一定规则进行的一系列转换,最后得到函数值,按照λ换位演算能得到函数值的函数称为λ可定义函数。λ换位演算是由λ项所组成的一种数学演算系统。λ换位演算是1935年由A.church提出用于精确定义可计算性的一种理论。
(3)递归函数是一种数论函数,在其中引入了“递归”概念后所定义的函数称递归函数。递归函数的自变量与函数值均为自然数。递归函数中的最简单部分称原始递归函数,原始递归函数的组成如下:①零函数:函数值为0的函数C0;②后继函数:S(x);③投影函数:Pi(n);④原始递归函数的组合是原始递归函数; ⑤原始递归函数通过简单递归式所构成的函数是原始递归函数。
在原始递归函数上作适当扩充可构成部分递归函数,亦即是说,设g(y,x1,x2,…,xn)是原始递归函数,如存在z使g(x1,x2,…,xn,z)=0,就取f(x1,x2,…,xn)值为满足g(x1,x2,…,xn,z)=0的最小的自然数z; 如不存在使g(x1,x2,…,xn,z)=0的自然数,就称f(x1,x2,…,xn)无定义。将此f加到原始递归函数中就得到部分递归函数。可以证明部分递归函数是可计算函数。
在20世纪30年代以后陆续证明了图灵机、λ可定义函数以及部分递归函数它们都是等价的,同时Church还提出了一个著名的Church论题,该论题说:λ可定义函数与一般直观所理解的可计算函数是相同的。这样就得到了可计算的三个数学模型:图灵机、λ换位演算及部分递归函数。此外,以后还有Markov提出的正规算法、Post提出的Post演算等,它们也都是可计算的数学模型。
由于计算机是一种可计算模型,数据库的模型也是可计算模型,因此,可计算性理论对计算机科学及数据库的影响与作用极其深远,而一般而言,不可计算函数一定不能在计算机中求解。
在线咨询
