计算与计算模型概论

计算与计算模型

引入

德国数学家希尔伯特（Hilbert）提出：是否存在着一个通用过程，这个过程能用来判定任意数学命题是否成立。即，输入一个数学命题，在有限时间内，如果这个命题成立，得到一个证明；或如果这个命题不成立，则得到一个反例。

图灵证明了对于平面几何来说，存在这样的过程。但是，对于一般的数学命题，不存在这样的过程。

计算的图灵定义

计算的图灵定义为这样的一个过程：输入 — 执行过程（有限步内结束）— 输出。其中，执行过程即为算法。其关键在于有限步内结束。

图灵给出了过程的科学定义，区分了可计算的问题和不可计算的问题。不可计算的问题比可计算的问题要多得多，但很难给出不可计算问题的例子。

理论上，可计算的问题都是可以被运用在实际生产的（有限时间可解）。但实际计算中，有时间需求、空间需求，计算要满足一定的需求，否则为理论上可行，但实际上不可行的计算。实际可行计算指的是可以引用在实际生产的计算过程。Cook 和 Karp 提供了实际可行的计算的标准，即多项式时间算法标准，区分了实际可计算的问题和实际不可计算的问题。实际可计算问题称为多项式时间可计算，实际不可计算的问题称为指数时间可计算（因为 Cook-Karp 研究的对象都是可计算问题）。这也就是 Cook-Karp 论题：一个算法实际可行当且仅当它是多项式时间可计算的。

那么，是否任意一个算法都可以用一台图灵机来执行呢？（即转换为一个模型计算，Church 论题）

显然，计算模型有两个需求:

• 可以形式化地表示算法（用符号串表示算法）
• 可以机械地执行算法

图灵机

图灵关于计算装置的设计：

• 用一套符号体系来表示信息，包括基本符号表
• 证明最小的基本符号集有二个基本符号，即用 0 和 1 可表示任意符号串（信息串）
• 有读写介质，可以抽象成为一维的线性数据带

这一装置即为图灵机。

计算模型在图灵机上的运行要求：

• 能够输入输出
• 有信息处理状态，可以用状态转移来表示过程的不同步骤
• 状态转移有一定的规则
• 实施的算法是一个状态的转移序列

看起来和有限自动机很像，但图灵机的存储空间是无限的、可修改的，其可能的总配置都是任意大的。图灵机描述的语言是递归可枚举语言，因此比 FSM 具有更强的计算能力。实际上，图灵机和我们建造的任何计算机一样强大。

其他类型的图灵机

• Lambda 演算（$\lambda$-演算）理论：Lambda演算理论是一个形式系统，同图灵机一样可作为计算模型，是语义学的理论基础。