计算、程序和机器

计算、程序和机器

译自：《An Introduction to the Theory of Computation 》by Eitan Gurari

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

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

Preface

计算（Computations）是为解题而设计的。程序（Programs）是描述计算的载体，机器（computers）是执行程序的装置。计算机科学领域关注两个对象——程序和机器。“程序”包括研究程序设计的方法论，比如算法、数据结构和编译原理等；“机器”包括研究执行程序的机器的开发方法，比如操作系统（KEMIN:OS了实现虚拟机器，机器涵盖了机器指令及其操作的数据的性质）。因此可得，程序、机器、问题（problems）和计算是计算机科学的核心课题，全面厘清它们的性质非常重要。性质包括属性和关系。

本书探索与程序、机器、问题和计算相关的一些重要概念。这些探索会转为对数学理论和模型的研究，比如自动机和形式语言。理论和模型提供一种简便的研究手段，因为理论和模型忽略不相关的细节。

第一章涉及一些基本概念的定义。首先是符号串（strings）的概念，符号串作为物化信息的角色；接着是符号串与[语言 ]的关系，并且介绍用来刻画语言的语法。

语言确切是什么？

Programming languages

A programming language is a formal language endowed（捐赠, 赋予, 捐助） with semantics that can be used to control the behavior of a machine, particularly a computer, to perform specific tasks. Programming languages are defined using syntactic and semantic rules, to determine structure and meaning respectively.

Programming languages are used to facilitate communication about the task of organizing and manipulating information, and to express algorithms precisely. Some authors restrict the term "programming language" to those languages that can express all possible algorithms; sometimes the term "computer language" is used for artificial languages that are more limited.

这一章接着引入一类程序，这类程序设计的原则是它足够的一般，从而可以作为所有的程序的模型；并且它也足够的原始，从而简化对程序的研究。

特别地，不确定性（nondeterminism ）的概念也通过程序来介绍。这一章最后探讨了问题（problems）的概念、问题与程序的关系等。

第二章……

程序与语言

我们无时无刻都在和信息打交道，时刻在处理信息和执行生活程序，这些程序存在于家中、办公室、图书馆、医院和学校等。不过，我们一般不会意识到自己原来在某程度上是一台执行程序的计算机。

为了应付生活中不同维度的编程需要，各种不同的编程语言被设计和开发出来了。这些编程语言的多样性只体现在信息（数据信息和操作命令信息）不同的解释，从表达计算的能力的角度看，这些编程语言区别不大。因此，研究[程序]的任务可转为研究[编程语言]代之。

透过细究[程序 ]所使用的[编程语言] （programming language）来间接地研究程序（programs ）是有裨益的。因为可以统一地通过[编程语言]来研究[程序]的本质。不过，所选择的语言应足够的通用（general）和原始（primitive），以便于讨论研究。

程序的形式定义

[程序 ]可定义为作用于[域 ]D上的有限[指令 ]序列。域D（称为变量的域domain of the variables）被假设为一可互相区别的元素的集合，集合元素称为变量的初始值（initial value of the variables）。D中的每一个元素被假设为程序变量的可能的取值。由此可得，第一，程序与某个[作用域]一一关联；第二，程序由[指令]组成；指令由[操作码]和[操作值]组成。操作码是[机器]可认别的信息（预定的操作语义），操作值是机器可操作的对象。

指令与机器

In computer science, an instruction is a single operation of a processor defined by an instruction set architecture.

指令 ：指定计算机的操作和操作数或操作数地址的一组字符代码。由操作码和地址码组成。可被中央处理机理解和执行。操作码规定计算机操作的性质，地址码指出操作数所在地址和操作结果要送往的地址。参见“指令系统”。

指令系统 ：一台计算机所能执行的各种不同类型指令的总和。即一台计算机所能执行的全部操作。不同计算机的指令系统包含的指令种类和数目也不同。一般均包含算术运算型、逻辑运算型、数据传送型、判定和控制型、输入和输出型等指令。

机器 ： 由零件装成、能运转、能变换能量或产生有用的功的装置。机器可以作为生产工具，能减轻人的劳动强度，提高生产率。

程序的指令

假设程序的指令有如下的一些：

1. 读指令：

read x

2. 写指令：

write x

3. 确定的赋值指令（Deterministic assignment） ：

y := f(x1, . . . , xm)

其中x1, . . . , xm, 和y 是变量，f 是从 D^m 到 D的函数（D^m是从D取出m个元素组成的排列，y取值也在D内）

4. 单分支控制指令

if Q(x1, . . . , xm) then I

where I is an instruction, x1, . . . , xm are variables, and Q is a predicate(谓语, 述部) from D^m to {false, true}.

5. 确定的循环控制指令

do

a

until Q(x1, . . . , xm)

where a is a nonempty sequence of instructions, x1, . . . , xm are variables, and Q is a predicate from D^m to {false, true}.

6. 条件接受指令（Conditional accept instructions）

if eof then accept

7. 拒绝指令（Reject instructions）

reject

8. 非确定的赋值指令（Nondeterministic assignment）

x := ?

where x is a variable.

9. 非确定的循环控制指令

do

a1

or a2

or ....

or ak

until Q(x1, . . . , xm)

where k >= 2, each of a1, . . . , ak is a nonempty sequence of instructions, x1, . . . , xm are variables, and Q is a predicate from D^m to {false, true}.

原文

In each program the domain D of the variables is assumed to have a representation over some alphabet. For instance, D can be the set of natural numbers, the set of integers, and any finite set of elements. The functions f and predicates Q are assumed to be from a given "built-in" set of computable functions and predicates (see Section 1.4 and Church's thesis in Section 4.1).

程序的作用域取自某个有限的[信息对象]范围，并且透过某字母表进行物化（representation）。比如，D可以是取有限个自然数、整数组成。函数f和谓词Q是假定的机器内置（built-in）的可计算函数和谓词。

In what follows, the domains of the variables will not be explicitly noted when their nature is of little
significance(重要性, 重要; 意思; 意义). In addition, expressions in infix(插入词; 中缀) notations will be used for specifying functions and predicates.

然后，如果变量的性质细节不是十分重要，变量的值域不会显式提及（explicitly noted）。另外，中缀形式的表达式（expressions in infix notations）用来表达[函数]和[谓词]。

请看如下一个确定型程序例子：

read x
y := 0
z := 1
do
    y := y + 1
    z := z + 1
until z = x
read y
if eof then accept
    reject

以上程序的作用域假定为自然数，并且以0为初始值。程序中使用了三个变量x, y, 和z，还有两个函数，常量函数f1() = 0和一元函数f2(n) = n + 1。循环指令使用了等价性的真值谓词（binary predicate of equality）。

程序的输入（input ）

程序的输入（input ）是指程序中的变量（variables）在值域的取值序列。程序可能有多个输入变量，多个变量组成变量组，变量组的一个取值为一个输入。

程序的执行（execution）

程序的一次执行指是机器读入程序的输入，赋于程序指令的具体语义后实际执行的确切过程，有动态性或时间性。这个过连续不间断的，并且是每一步是确切的，唯输入值一的。如果不是完会确切的不算是同一次程序执行。

确定型程序（Deterministic Programs）

[确定型程序]是程序的输入与程序的执行（过程）一一对应的。也就是说，程序的同一个输入会产生相同的[执行]。非定型程序则反之。

[读指令]read x的执行语义是（告诉机器）把下一个[输入值]读到变量x。[写指令]write x的执行语义是（告诉机器）把变量x输出；
赋值指令和条件分支指令是机器内置指令，有约定的执行语义。

[循环控制指令]的执行语义复合了循环执行do指令序列语义和检查谓词Q(x1, . . . , xm)真值的语义。循环控制指令的循环执行直到谓词Q(x1, . . . , xm)值为真。

[条件接受指令]告诉机器当所有输入都处理完毕后停掉（halt）执行，输入完毕指输入到达了输入文件的尾端EOF。如果EOF为假，输入未处理完则继续执行（条件接受指的）后续指令。同样的，机器在遇到以下情形也会停掉（halt ）程序执行：

• 执行reject指令
• 执行越界读取指令（KEMIN：这个操作怎么检查的？）
• 执行程序外的指令
• 执行计算域外值的指令（比如除0）

例子

do
    read value
    write value
until value < 0
if eof then accept

The execution sequences of the program in Figure 1.3.2(b) halt due to the conditional accept instruction,
only on inputs that end with a negative value and have no negative values elsewhere (e.g., the input "1, 2, -3"). On inputs that contain no negative values at all, the execution sequences of the program halt due to trying to read beyond the end of the input (e.g., on input "1, 2, 3"). On inputs that have negative values before their end, the execution sequences of the program halt due to the transfer of control beyond the end of the program (e.g., on input "-1, 2, -3").

很显然的，accept 指令可以被看成停机指令（halt command），宣告程序的执行成功完成，因为accept 只在输入处理完后被执行。同样的，reject指令也可以被看成停机指令，宣告程序的执行没有成功完成。

The requirement that the accept commands be executed only after reading all the input values should cause no problem, because each program can be modified to satisfy this condition. Moreover, such a constraint seems to be natural, because it forces each program to check all its input values before signaling a success by an accept command. Similarly, the requirement that an execution sequence must halt upon trying to read beyond the end of an input seems to be natural. It should not matter whether the reading is due to a read instruction or to checking for the eof predicate.

accept指令（be executed only after reading all the input values ）的设计需求和哲学原因是很自然的，无任何疑问，因为每一个程序都可被修改来满足这个条件。另外，这个约束（constraint ）很自然的需要的第二个原因是它强迫程序在宣告成功完成执行前逐个检查遍所有输入值……

KEMIN:accept指令或reject指令都是机器的[控制信息 ]，控制机器停机操作，与其它流程控制指令是相同性质的。 请看如下编程语言的定义：

A programming language is a formal language endowed（捐赠, 赋予, 捐助） with semantics that can be used to control the behavior of a machine , particularly a computer, to perform specific tasks.

要注意，条件分支指令和循环指令的谓词Q(x1, . . . , xm) 与EOF逻辑区别。谓词是变量的x1, . . . , xm一个组合逻辑值，这个值是机器的[控制信息 ]，不是程序的输入值——被控制对象。

Computations

Programs use finite sequences of instructions for describing sets of infinite numbers of computations. The descriptions of the computations are obtained by "unrolling" 解开; 打开the sequences of instructions into execution sequences. In the case of deterministic programs, each execution sequence provides a description for a computation. On the other hand, as it will be seen below, in the case of nondeterministic programs some execution sequences might be considered as computations, whereas others might be considered noncomputations. To delineate this distinction we need the following definitions.

程序透过使用有限的指令序列来描述无限的计算。“计算”通过指令序列的动态执行得到解释和描述。

如果程序的[执行 ]终止于accept指令，我们称该次执行为[接受计算 ]（accepting computation），否则称为[非接受计算 ]（nonaccepting computation ）或拒绝计算（rejecting computation）。接受计算和非接受计算统称[计算 ]（computation）。

A computation is said to be a halting computation if it is finite.

如果程序对基于某个输入值有一个接受计算，我们称该输入值被程序接受或被程序识别；否则称输入值被程序拒绝或不能被识别

如果程序P对输入值x是一个接受计算，并产出输出y，那么我们称y是程序P基于x的输出。否则，程序对x是一个nonaccepting 计算时，即便有执行write指令，输出outputs均为无定义。

Nondeterministic Programs

基于不同的目的和需要，编程语言中纳入了非确定的指令。其中一个目的是允许程序为问题提供多于一个的解决方案。非确定指令达到了这个目的。另一个目的是为了划分困难问题，把困难问题归类为不同类的程序进行研究。

Guessing in Programs

每一个程序的语义透过程序的计算进行刻画。确定型程序的语义可以直接由程序的指令刻画。也就是说，程序的语义既可通过计算综合地刻画，又可以通过具体指令的执行来具体地刻画，因为程序是确定型的。

而非确定型程序则要区分程序的执行与计算。非确定型程序的语义只能通过具体指令的执行来具体地刻画。因为虽然非确定型程序的每一次计算都是通过执行程序指令实现的，但是有一部分执行是不与任何程序计算一一对应的。这部分计算就是执行非确定指令的原因。

程序可想像成与一部魔幻机器关联着，机器负责执行程序指令。确定型机器就像一台没有自由的机器，很死板，只按指令规矩执行；而非确定型机器则除了执行指令的本地语义，还要满足全局语义——到达accept指令。(original:http://blog.csdn.net/keminlau/archive/2009/12/13/4994687.aspx)

Configurations of Programs

An execution of a program on a given input is a discrete process in which the input is consumed, an output is generated, the variables change their values, and the program traverses its instructions. Each stage in the process depends on the outcome of the previous stage, but not on the history of the stages. The outcome of each stage is a configuration of the program that indicates the instruction being reached, the values stored in the variables, the portion of the input left to be read, and the output that has been generated so far.

Consequently, the process can be described by a sequence of moves between configurations of the program.