or

这个表是：

或者

（最后一行末尾的句号是以“这个表是……”开头的句子的一部分。）这个表暗示 ( x)是机器的另一个m-格局。从下面的推广可以看出， ( x)同样也是机器的另一个m-格局。

Or, in greater detail:

或者，更详细地表示为：

（同样，最后一行之后的句号表示这个表被当成了句子的一部分。）注意，擦除字符后，转向 已经是这台机器的一个m-格局了，因此，不会导致m-格局的无限产生。

In this we could replace x) by and then give the table for (with the right substitutions) ad eventually reach a table in which no m-functions appeared.

这里，我们使用 代替 x)，然后给出的表（进行适当地代换），最终可以得到一个不包含任何m-函数的表。

正如图灵使用来代表格局(, x)一样，他还可以使用表示，x), 使用其他的格局来表示和。

现在，我们已经掌握了这些函数（才怪！），图灵不断地积累这些函数。我知道，现在我们很难看出这些函数是如何恰当地搭配在一起的。为了构造通用机，图灵需要一些操作单个字符或字符串的通用类型的函数。读者已经看到了查找和擦除函数。他还需要剪切、复制、粘贴和一些标准打印函数。

函数表示“在结尾打印”。它在第一个空的F-格处打印β表示的符号。

这个函数隐藏着一些假设。通常情况下，寻找其第三个参数在最左边的第一次出现，但是这里的第三个参数是一个中央元音，它也是为到达序列最左边所要寻找的符号。于是，正如图灵在第85页给出的第二个机器的例子，函数也假设每行中存在两个中央元音。这个m-函数首先找到这两个中央元音中最右边的一个（出现在E-格的那个），然后把读写头左移置于左边F-格的中央元音处。随后，函数 沿着F-格向右移动，直到找到一个空格，并在此打印一个β字符，对于大多数计算机器来说，这个β将是0或1。

接下来的例子都很有技巧。图灵首先定义了两个名字分别为 （指左边的）和 （指右边的）的函数，然后分别用它们与结合得到另外两个函数和。这两个新的函数在找到所需字符后会将读写头向左或者向右移动。

我本应该把它们称为和，而非和，但那只是我的想法。

通用机会要求把字符从纸带的一个位置移动到另一个位置上。函数的功能是“复制”。字符α更可能是一个标记。首先找到这个标记左边的F-格里的字符，然后使用将该字符复制到尾部第一个空的F-格中。

注意上面的函数使用来寻找字符α，因此操作结束的时候读写头位于标记的左边，正好是这个标记指示的字符处。

函数的语法比较独特：扫描到的字符成为了的第二个参数。图灵说：

[238]

The last line stands for the totality of lines obtainable from it by replacing β by any symbol which may occur on the tape of the machine concerned.

最后一行代表了用机器纸带上可能出现的任意符号代替β后得到的所有的行。

例如，如果函数只用来复制0或1，那么事实上，会被定义成：

函数代表了“复制并擦除”。它也有分别包含两参数和三参数的版本。

带三个参数的首先使用复制最左边被α标记的数字，然后使用擦除这个标记。带两个参数的则使用三参数版本的函数来复制第一个数字并擦除标记，然后再转向两参数版本的函数。实际上，所有标记为α的符号都被复制到纸带尾部第一批可用的F-格里。（在第77页图灵的第二个例子中，本可以使用这个函数把一连串的1复制到纸带的尾部。）

是时候提出效率这个令人生畏的问题了。图灵定义的函数看上去很精密紧凑，但事实上里面隐藏着巨大的工作量。为了执行一次复制和擦除，函数要使用来寻找标记（并记住要一路回溯到哨兵），然后再使用，而又要调用来找到相同的标记后才能将其擦除。一种更高效的方法是使用在第一次找到某个标记，并在复制字符之前就将其擦除。（为了纪念图灵机臭名昭著的低性能，我们使用“图灵沥青坑”^［2］一词来描述过度一般化的计算机例程，准备这些例程比运行它们花费的时间更多。）

但是，图灵并不关心效率问题，毕竟，机器都是想象出来的。如果他愿意，可以以10⁶ ZHz^［3］的频率来运行机器，没有人会考虑做了多少无用工。

函数是指“替换”。假设参数α和β都是标记。函数找到最左边的α，并用β替换它。（因为图灵不允许替换已经在F-格中标记的字符，因此我们可知α和β是标记。）

三参数版本的函数用β替换所有的α标记。

为了保持一致，右边的解释部分的第一行应该缩进两个字符。

如果你已经熟悉了图灵的方法和命名规则，就会知道下面这个函数是用来完成“复制和替换”的。

图灵论文的其他地方没有使用到这些函数。

通用机要求有“搜索并替换”功能，于是图灵接着用了半页的篇幅展示了（“比较”）和 （“比较并擦除”）函数。由于这些函数里的最终m-格局太长，因而图灵的解释没有放在每个表的右边，而是放在了下面。（第一行有个错误：最终m-格局列中的下标1应该是逗号。在该列出现的一些句号也没有任何意义。）

The first symbol marked alpha; and the first marked β are compared. If there is neither α nor β, → If there are both and the symbols are alike, → Otherwise →

differs from α, β) in that in the case when there is similarity the first α and β are erased.

α, β). The sequence of symbols marked α is compared with the sequence marked β → if they are similar. Otherwise → Some of the symbols α and β are erased.

比较第一个α标记的字符和第一个β标记的字符。如果即没有标记α也没有标记β，则→。如果标记α和β都存在，并且所标记的字符一样，那么→；否则→。

与 α, β)的不同之处在于，如果存在一对相同的字符，那么第一个α和β将被擦除。

α, β)，比较α标记的符号序列和β标记的符号序列。如果它们是相似的，则→；否则→。一些α和β将被擦除。

图灵在这里所说的“相似”是指“完全相同”。

现在，图灵已经用完了他能想到的容易记忆的所有函数名称，因为他把接下来的函数仅简单命名为。不幸的是，这也是一般情况下他用来表示m-格局的字母；更糟糕的是，后文中他使用来指代这个函数。

我相信，图灵本意是想用来命名这个函数，而不是用。类似函数用来寻找某个符号（最左边）的第一次出现，这个函数是用来寻找某个符号（最右边）的最后一次出现的。用两个连续的字母来表示有关联的两个和函数是有意义的，因此，尽管接下来的表里描述的是函数，我将使用来指代该函数。

只有一个参数的函数将读写头右移，直到它在一行中找到两个空格。我们假设那里处于纸带的最右端。带两个参数的函数首先使用只有一个参数的，然后再向左移动寻找字符α。

[239]

在本节的最后，图灵给出了一些名字很熟悉的辅助函数。

回想一下，函数用来在最后一个F-格中打印一个字符。函数2在最后两个F-格中打印两个字符。

类似地，函数用来将α标记的字符复制到尾部。函数2则复制α和β标记的字符，函数3复制α、β和γ标记的字符。

这些复制是顺序执行的：首先复制所有α标记的字符，其次复制所有β标记的字符，以此类推。图灵使用了带6个参数的函数，这个函数虽然之前没有描述过，但是它的操作是显而易见的。

最后，只有一个参数的函数擦除所有的标记。

年长点的程序员可能知道一本由Pascal语言的创始人尼克劳斯·威茨（1934—）编著的书，书名非常美妙，叫作《算法+数据结构＝程序》（Prentice-Hall，1975年出版）。顾名思义，一段计算机程序包括代码（算法）和代码处理的数据。至此，图灵已经展示了他的通用机所需的诸多算法，但是还没有描述如何让一台计算机器来成功地处理数据。这就是接下来要讲的内容。