计算机状态与算法讨论

姜咏江

在维基百科上提问What is Algorithms? 得到的回答是No results found at Wikibooks.想必是西方还无人给算法下一个定义。在《算法导论》这本书中给出的是描述性的阐述:

Informally, an algorithm is any well-defined computational procedure that takes

some value, or set of values, as input and produces some value, or set of values, as

output. An algorithm is thus a sequence of computational steps that transform the

input into the output.

这种将算法描述成将输入转化成输出计算步骤的序列的形式不能算算法的定义。广义地讲，算法应该是用符号文字等描述解决问题的一种方法。面对现代计算机，就是用文字符号进行程序设计的方法。本文仅就计算机的状态、状态变化与算法的关系进行探讨。

在计算机CPU设计中，将计算机各种组成设备按照时钟节拍保持的状态，统一起来称为计算机的状态。计算机的设备都有控制状态变化的控制线。控制线只能取值0或1，因而是逻辑变量。计算机的全部控制线排成一个序列字，叫计算机控制字。由于计算机设备的状态都是有限的，由计算机设备的有限性可知，控制字每个机器节拍会取一个有限位数的二进制数，这样就会决定计算机的一种状态。因为n位的二进制数码排成的数最多有2ⁿ个，故具有n位长度计算机控制字的计算机共有2ⁿ个不同的状态。

计算机的状态可以依据用途进行分类。例如输入状态、输出状态、运算状态、控制状态和存储状态等。但不论如何划分状态的类型，一个计算机的基本状态是固定的，除非改变计算机的组成设计。

由于计算机的全部控制线在计算机运行中的每一个节拍都有确定的值，而控制字的值又可以通过指令的方式加以改变，所以计算机的状态转换可以通过指令来加以控制实现。指令就是一种符号，计算机有指令译码器和控制逻辑等，将指令变成一系列预先定制好的控制字值序列，通过这个控制字值序列，就可以指挥计算机的状态按预先设计的状态变化。

计算机的基本状态虽然有限，但我们可以通过给出不同的指令系列，来组织计算机的状态变化序列。这种状态变化序列可以具有任意性。由于指令系列的长度可以是任意的，因而在一个指令序列的决定之下的状态系列长度，可以随着指令系列的长短伸缩。由于指令系列有分支、循环等形式，故计算机的状态序列也会依据指令序列实现变化。

算法是解决问题的方法。通过计算机实现的算法，要能够解决问题，引起计算机状态变化的序列长度就不能是无止境的。因而在某问题利用指令书写的算法程序将产生无限长的状态变化序列，那么这个问题在计算机上就没法解决。例如，所谓的死循环程序就是这种情况。

如果用计算机解决了某个问题，我们就说该问题在计算机上有解，反之则称为在计算机上无解。

计算机基本状态是有限的集合，这与算法程序执行的计算机状态序列可以是无限的状态变化并不矛盾。计算机基本状态集合表达了不同状态的存在性，而算法程序执行所经历的状态变化是对基本状态的选择使用性问题，两者是完全不同性质的问题。如果将它们之间进行状态数量上的比较，就会犯不同性质事物之间统一量化的错误。

对计算机来说，基本状态是结构性的概念，而算法是对基本状态使用性的概念。

图灵机与现代计算机一样也有基本状态和使用状态之分。图灵机的基本状态十分简单，可分为读、查表、写、左移、右移、不移等状态。这些状态的选择是通过有限字符集的字符输入来实现的。

图灵机的状态转移表实际上就是用图灵机解题的一种算法。这种算法用输入的字符来控制图灵机的基本状态转移，从而形成了各种状态转移序列。包括中间产生输入字符在内的输入字符序列，如果使图灵机状态序列长度有限，并最终被接受，那么就可以认为全部输入输出的字符序列构成了有解的问题；如果图灵机产生的状态序列长度无限，或最终不被接受，那么不论输入输出字符序列如何，都称为该问题在图灵机上无解。

对图灵机来说，如果不论输入何种字符，都会在基本状态中任意选择，这就给人产生了一种状态的不确定性。这种情况一般都发生在试图判定某个问题是否在图灵机上可解的时候。这种判定的情况要随机地组织状态变化序列，对所有可能产生的状态序列进行测试。一旦碰上验证条件成立，那么就可以断定该问题在图灵机上有解。如果在一个图灵机的允许的使用状态变化序列长度有限，这就是一个确定型图灵机，否则就是一个非确定型图灵机。

2015-06-04