信息、状态和控制的关系（头脑风暴）

刘建文略译（http://blog.csdn.net/keminlau ）

KEY:信息处理 计算理论 形式语言 编程语言

信息、状态和控制的关系

计算的两本质元素是，第一，状态的操控；第二，操控的时间流程。

接着要计算什么，然后涉及[状态的表达]和[操控流的有目的安排]，前者是数据，后者是程序。

计算主体与计算客体

我 们说，计算涉及状态的操控和这种操控的有目标的安排，那操控由谁来主导呢？答案是一个称为计算主体的东西在主导计算过程。计算主体表现形式有自动机、人等 有一定逻辑判断能力的对象。计算主体必须能识别操作指令的操作语义（无论原始的还是非原始的），确切执行操作语义所对应的对计算客体所作的状态变更。

举一实例来理解

程序是什么？第一，程序与某个[作用域]一一关联；第二，程序由[指令]组成；指令由[操作码]和[操作值]组成。操作码是[机器]可认别的信息（预定的操作语义），操作值是机器可操作的对象。

程序与机器的关系

第 二章探讨有限记忆的程序（finite-memory programs）。状态（state）的概念被用来对有限记忆程序内的位置（location ）进行抽象和对程序的变量的赋值（assignment ）的抽象。状态的概念是用来展示如何将有限记忆的程序建模成一种抽象计算机，叫有限状态换能器（transducers）。换能器的本质是一集状态和转换 该集状态的操作规则的组合。有限记忆程序的输入（或者有限状态换能器所识别的语言）由一种特定的语法来刻画，这种语法叫正则语法（regular grammars）。
Computer programs that use no auxiliary memory, except for holding the input and output values, are by definition examples of finite-memory programs.

“算法步具体进行”就是状态的准确操控

抽象地说，所谓计算就是从一个符号行a得出另一个符号行b。譬如说从符号行12+3(这是由1、 2、+及3等四个符号组成的符号行）得到15(这是由1和5两个符号组成的符号行），这个计算就是加法。
所谓从a得到b 是指能够从a出发，在有限步内真正具体求出b。 计算必须是能够具体进行的 。

带、读写头、控制器是状态操控及操作流的实现形式，非本质的

把Turing机描写成一种机械装置，如带、读写头、控制器等等，其实是不必要的。对于理兮解Turing机来说，或者对子把Turing机作为一种理论研究的工具来说，都是不必要的。正如前边的例子中所看到的那样，如果把内部状态看作符号行的一部分，所谓 Turin机的计算实际上不过是一种符号行的变换 。

Turing机假定机器只有一条带，一个读写头，而且读写头又只能一个格一个格移动。这相当于只有一个寄存器，数据都储存在一条带上，又只有一种存取方式。这 与实际计算机距离很远，效率也太低 ，即使作为理论研究的工具也是很不方便的。还有，Turing机的指令系统与程序同计算机的 指令系统与程序也大不相同 。从五十年代以来，由于受到计算机发展的影响，对Turing机提出了种种修改。这些变形Turing机或者增加带和读写头的数目，或 改变指令及程序的形式 。

这些修改有两个方面。

第一是计算方式。Turing机的计算方式极为原始，即使一个个很简单的函数，用它来算也可能非常麻烦。因为Turing机的一切计算只能通过一个读写头进行，而且这个读写头每次只移动一格。 第二方面的修改是程序或指令的形式。修改Turing机的 程序或指令的形式 使它更接近于电子计算机的程序。

图灵机内部状态的意思

电子计算机的程序由一条一条指令组成，如果不是碰到转移指令，那么在执行了第 i 条指令之后就执行第 ( i + 1)条指令。但若碰到转移指令，那就执行具有一定标号的指令。Turing机的内部状态在一定程度上也起了标号的作用。实际上Turing机的每条指令都 有两个部分： 运算指令及转移指令 。

一个Turing机相当于一个专用计算机，它进行一种特定的计算，或者说，它计算一个特定的函数。这与近代通用电子计算机不同。 通用电子计算机是输入程序及数据 ，然后按程序进行计算，这个 计算是由该程序确定 的，而 不是由计算机确定 的。 通用Turing机也正是如此。所谓通用Turing机U是一个Turing机，对它输人的不只是数据，还有某个Turing机T的Godel数t。因 此，U的输入是数组<t, x>，t是Turin机T的Godel数(即T的程序)，x是一个输人数据。U对这个数组的计算等同于Turing机T对输入x的计算。所以只要对 U输入任何专用机T的程序，U可以进行T的计算。

Turing机实际上就是一个程序 ，那么，通用Turing机也是一个程序。它是什么样的程序？电子计算机的一个普通的应用程序，其作用是对于给定的输入数据x，可以计算出一定的结果，即得到输出y。电子计算机的解释程序则不然。所谓解释程序，其作用如
下：给定任何一个应用程序(用高级语言书写的)以及输入数据，利用解释程序就可以得到输出。因此， 通用Turing机作为一个程序，在某种意义上相当于一个解释程序 。