可计算理论的研究内容及应用

摘要

可计算理论建立于二十世纪三十年代.可计算理论的研究对象有三个:(1)判定问题;(2)可计算函数;(3)计算复杂性.判定问题主要是判定方程是否有解;可计算函数主要讨论一个函数是否可计算,建立了原始递归函数、图灵机等许多数学模型判定一个函数是否属于可计算函数;计算复杂性主要讨论的问题是P=?NP.可计算理论的计算模型主要包括:(1)Turing机;(2)递归函数;(3)λ演算;(4)POST系统;(5)正则算法.可计算理论是理论计算机科学,属于计算机科学的基础研究领域,可计算理论是计算机软件工程、系统结构、并行运算、图像处理、人工智能、网络的数学理论基础和工具.