我的博客已经搬家到  xiongbox.com   欢迎访问！

本文永久链接 http://xiongbox.com/可计算性理论的简单小结/

1.可计算性理论研究计算的一般性质的数学理论，也称算法理论或能行性理论。它通过建立计算的数学模型（例如抽象计算机），精确区分哪些是可计算的，哪些是不可计算的。

2.计算的过程就是执行算法的过程。可计算性理论的重要课题之一，是将算法这一直观概念精确化。算法概念精确化的途径很多，其中之一是通过定义抽象计算机，把算法看作抽象计算机的程序。通常把那些存在算法计算其值的函数叫作可计算函数。因此，可计算函数的精确定义为：能够在抽象计算机上编出程序计算其值的函数。这样就可以讨论哪些函数是可计算的，哪些函数是不可计算的。

3.图灵机是一种在理论计算机科学中广泛采用的抽象计算机，用于精确描述算法的特征。可用一个图灵机来计算其值的函数是可计算函数，找不到图灵机来计算其值的函数是不可计算函数。可以证明，存在一个图灵机Ｕ，它可以模拟任何其他的图灵机。这样的图灵机Ｕ称为通用图灵机。通用图灵机正是后来出现的存储指令的通用数字计算机的理论原型。

4.图灵机的停机问题是不可判定的，即不存在一个图灵机能够判定任意图灵机对于任意输入是否停机。图灵机的停机问题是半可判定的。图灵机的停机问题是很重要的，由它可以推出计算机科学、数学、逻辑学中的许多问题是不可判定的。

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