|
研究计算的可行性和函数算法的理论。又称算法理论。它是算法设计与分析的基础，也是计算机科学的理论基础。可计算性是函数的一个特性。设函数f的定义域是D，值域是R ，如果存在一种算法 ，对D中任意给定的x ，都能计算出f（x）的值，则称函数f是可计算的。 研究计算的一般性质的数学理论，也称算法理论或能行性理论。它通过建立计算的数学模型（例如抽象计算机），精确区分哪些是可计算的，哪些是不可计算的。计算的过程就是执行算法的过程。可计算性理论的重要课题之一，是将算法这一直观概念精确化。算法概念精确化的途径很多，其中之一是通过定义抽象计算机，把算法看作抽象计算机的程序。通常把那些存在算法计算其值的函数叫作可计算函数。因此，可计算函数的精确定义为：能够在抽象计算机上编出程序计算其值的函数。这样就可以讨论哪些函数是可计算的，哪些函数是不可计算的。 可计算性理论起源于对数学基础问题的研究。20世纪30年代，为了讨论是否对于每个问题都有解决它的算法，数理逻辑学家提出了几种不同的算法定义。K.哥德尔和S.C.克林尼提出了递归函数的概念，A.丘奇提出λ转换演算,A.M.图灵和E.波斯特各自独立地提出了抽象计算机的概念（后人把图灵提出的抽象计算机称为图灵机），并且证明了这些数学模型的计算能力是一样的,即它们是等价的。著名的丘奇-图灵论题也是丘奇和图灵在这一时期各自独立提出的。后来，人们又提出许多等价的数学模型，如A.马尔可夫于40年代提出的正规算法（后人称之为马尔可夫算法），60年代前期提出的随机存取机器模型（简称 RAM）等。50年代末和60年代初，胡世华和J.麦克阿瑟等人各自独立地提出了定义在字符串上的递归函数。 可计算性理论是计算机科学的理论基础之一。早在30年代，图灵对存在通用图灵机的逻辑证明表明，制造出能编程序来作出任何计算的通用计算机是可能的，这影响了40年代出现的存储程序计算机（即诺伊曼型计算机）的设计思想。可计算性理论确定了哪些问题可能用计算机解决，哪些问题不可能用计算机解决。例如，图灵机的停机问题是不可判定的表明，不可能用一个单独的程序来判定任意程序的执行是否终止，避免了人们为编制这样的程序而无谓地浪费精力。 可计算性理论中的基本思想、概念和方法，被广泛应用于计算机科学的各个领域。建立数学模型的方法在计算机科学中被广泛采用。递归的思想被用于程序设计，产生了递归过程和递归数据结构，也影响了计算机的体系结构。λ演算被用于研究程序设计语言的语义，例如，表处理语言就以λ转换演算为理论基础。
|
|
|
