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

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