计算机科学导论：跨学科方法

5.3　普遍性

图灵机模型本质上是一个数学作品，它将有关计算的基本数学概念简化，以使我们可以得出精确结论。这项工作的基础是由图灵在他最初的论文里提出来的，但随后学者们不断地发展，直到今天我们被各种计算设施所包围，都有赖于图灵机模型得出的这些结论。图灵机有如此巨大的影响力，我们所有从事于计算的人（当然，也包括本书的读者）都有必要对其有个基本理解。在本节中，我们试图讲解图灵在那篇论文中提出的两个基本概念：一是一台通用目的的计算机可以进行任何计算；二是假设所有计算设备本质上是等价的。

算法　当我们写一个计算机程序时，我们通常是在设计一种可以解决某个问题的方法。这个方法必须依赖于程序环境，或者这个方法适用于很多环境。正是方法，而不是程序本身，带领我们一步步地解决问题。在计算机理论中，名词“算法”（algorithm）用来描述实现计算机程序中有限的、确定的、有效地解决问题的办法。算法是计算机科学理论中的核心领域。

在本书中，我们已经学习了很多算法，比如牛顿定理、欧几里得定理、归并排序、广度优先搜索等。这里给出的定义虽然不够严谨，但也足够说明这个概念。图灵机给数学家们带来了这个概念，并可用于数学证明。在这里，我们关注于这些重要的思路，而不再停留于定义及其完整版证明。

可判定性。假设我们在纸带上输入一个字符串并将一个图灵机处于启动状态，有四种可能的结果。该机器可能：

·停在标有“YES”的状态（接受输入字符串）。

·停在标记为“NO”的状态（拒绝输入字符串）。

·停在标有“H”的状态（停止，不再接受或拒绝）。

·以上都不是（进入无限循环）。

目前，当机器停机时（或处于无限循环中），我们会忽略纸带前后的内容。我们说一个图灵机识别某个语言，是指图灵机以这个语言的所有可能的字符串作为输入时，都会引导机器最终走到接受状态。同时，对于所有不在所识别的语言中的输入字符串，图灵机都会停止运行（终止于标记为“NO”或“H”的状态），那么我们就说这个图灵机可以判定（decide）该语言。对于每一个输入字符串，这个图灵机必须都能停机并且给出正确的答案。例如，我们在前一节末尾设计的二进制频率计数器图灵机能够判定（和识别）所有a和b数量相同的二进制字符串。注意：对于DFA，当DFA总是停止时，我们不需要区分判定和识别。 ...