On Computable Numbers, with an Application to the Entscheidungsproblem

Proceedings of the London Mathematical Society, Series 2, Vol. 42 (1936), pp. 230–265. [Received 28 May, 1936.—Read 12 November, 1936.]

《伦敦数学会会刊》（Proceedings of the London Mathematical Society）第 2 辑第 42 卷（1936），第 230–265 页。［1936 年 5 月 28 日收稿，1936 年 11 月 12 日宣读。］

（译注：本对照所据 PDF 为 1936 年原刊第 230–265 页的扫描本，不含图灵后来发表的更正“On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction”（Proceedings of the London Mathematical Society, Series 2, Vol. 43 (1937), pp. 544–546）。原刊中的排印错误一律照录，并在相应位置加译注。）

On Computable Numbers, with an Application to the Entscheidungsproblem

论可计算数及其在判定问题上的应用

By A. M. Turing.

A. M. 图灵（A. M. Turing）著。

The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means. Although the subject of this paper is ostensibly the computable numbers, it is almost equally easy to define and investigate computable functions of an integral variable or a real or computable variable, computable predicates, and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique. I hope shortly to give an account of the relations of the computable numbers, functions, and so forth to one another. This will include a development of the theory of functions of a real variable expressed in terms of computable numbers. According to my definition, a number is computable if its decimal can be written down by a machine.

“可计算”数可以简要地描述为：其小数表达式能用有限手段算出的那些实数。虽然本文表面上的主题是可计算数，但定义和研究以整数变量、实变量或可计算变量为自变量的可计算函数、可计算谓词等，几乎同样容易。不过，各种情形涉及的基本问题是相同的，我选择可计算数作明确处理，是因为它涉及的技术最不繁琐。我希望不久能阐述可计算数、可计算函数等等彼此之间的关系，其中将包括用可计算数来表述的实变函数论的发展。按照我的定义，一个数如果其小数能由一台机器写出，它就是可计算的。

In §§ 9, 10 I give some arguments with the intention of showing that the computable numbers include all numbers which could naturally be regarded as computable. In particular, I show that certain large classes of numbers are computable. They include, for instance, the real parts of all algebraic numbers, the real parts of the zeros of the Bessel functions, the numbers $\pi$, $e$, etc. The computable numbers do not, however, include all definable numbers, and an example is given of a definable number which is not computable.

在第 9、10 节中，我给出一些论证，意在表明可计算数包括了一切可以自然地被看作可计算的数。特别是，我证明某些很大的数类是可计算的，例如所有代数数的实部、贝塞尔函数零点的实部、$\pi$、$e$ 等数。然而，可计算数并不包括一切可定义的数；文中给出了一个可定义但不可计算的数的例子。

Although the class of computable numbers is so great, and in many ways similar to the class of real numbers, it is nevertheless enumerable. In § 8 I examine certain arguments which would seem to prove the contrary. By the correct application of one of these arguments, conclusions are reached which are superficially similar to those of Gödel†. These results have valuable applications. In particular, it is shown (§ 11) that the Hilbertian Entscheidungsproblem can have no solution.

† Gödel, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", Monatshefte Math. Phys., 38 (1931), 173–198.

尽管可计算数类如此之大，并在许多方面与实数类相似，它却是可枚举的。在第 8 节中，我考察了一些似乎能证明相反结论的论证。正确运用其中一个论证，可以得到表面上与哥德尔†的结论相似的结论。这些结果有重要的应用，特别是证明了（第 11 节）希尔伯特的判定问题（Entscheidungsproblem）不可能有解。

† Gödel, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", Monatshefte Math. Phys., 38 (1931), 173–198.

In a recent paper Alonzo Church† has introduced an idea of "effective calculability", which is equivalent to my "computability", but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem‡. The proof of equivalence between "computability" and "effective calculability" is outlined in an appendix to the present paper.

† Alonzo Church, "An unsolvable problem of elementary number theory", American J. of Math., 58 (1936), 345–363.

‡ Alonzo Church, "A note on the Entscheidungsproblem", J. of Symbolic Logic, 1 (1936), 40–41.

在最近的一篇论文中，阿隆佐·丘奇†提出了“能行可计算性”（effective calculability）的概念，它与我的“可计算性”等价，但定义方式截然不同。丘奇对判定问题也得出了类似的结论‡。“可计算性”与“能行可计算性”等价的证明，在本文附录中给出概要。

† Alonzo Church, "An unsolvable problem of elementary number theory", American J. of Math., 58 (1936), 345–363.

‡ Alonzo Church, "A note on the Entscheidungsproblem", J. of Symbolic Logic, 1 (1936), 40–41.

1. Computing machines

1. 计算机器

We have said that the computable numbers are those whose decimals are calculable by finite means. This requires rather more explicit definition. No real attempt will be made to justify the definitions given until we reach § 9. For the present I shall only say that the justification lies in the fact that the human memory is necessarily limited.

我们说过，可计算数是那些小数能用有限手段算出的数。这需要更明确的定义。在讲到第 9 节之前，我们不会真正尝试为所给出的定义辩护。目前我只想说，其理由在于人的记忆必然是有限的。

We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions $q_1, q_2, \ldots, q_R$ which will be called "$m$-configurations". The machine is supplied with a "tape" (the analogue of paper) running through it, and divided into sections (called "squares") each capable of bearing a "symbol". At any moment there is just one square, say the $r$-th, bearing the symbol $\mathfrak{S}(r)$ which is "in the machine". We may call this square the "scanned square". The symbol on the scanned square may be called the "scanned symbol". The "scanned symbol" is the only one of which the machine is, so to speak, "directly aware". However, by altering its $m$-configuration the machine can effectively remember some of the symbols which it has "seen" (scanned) previously. The possible behaviour of the machine at any moment is determined by the $m$-configuration $q_n$ and the scanned symbol $\mathfrak{S}(r)$. This pair $q_n, \mathfrak{S}(r)$ will be called the "configuration": thus the configuration determines the possible behaviour of the machine. In some of the configurations in which the scanned square is blank (i.e. bears no symbol) the machine writes down a new symbol on the scanned square: in other configurations it erases the scanned symbol. The machine may also change the square which is being scanned, but only by shifting it one place to right or left. In addition to any of these operations the $m$-configuration may be changed. Some of the symbols written down will form the sequence of figures which is the decimal of the real number which is being computed. The others are just rough notes to "assist the memory". It will only be these rough notes which will be liable to erasure.

我们可以把一个正在计算某个实数的人，比作一台只能处于有限个状态 $q_1, q_2, \ldots, q_R$ 的机器，这些状态称为“$m$-格局”（$m$-configurations）。机器配有一条穿过它的“纸带”（相当于纸），纸带被分成若干段（称为“方格”），每一段都可以承载一个“符号”。在任一时刻，恰有一个方格，比如第 $r$ 个，承载着符号 $\mathfrak{S}(r)$，它“在机器中”。我们可以称这个方格为“被扫描方格”，其上的符号称为“被扫描符号”。可以说，“被扫描符号”是机器唯一“直接意识到”的符号。不过，机器可以通过改变自己的 $m$-格局，有效地记住它先前“见过”（扫描过）的某些符号。机器在任一时刻可能的行为，由 $m$-格局 $q_n$ 和被扫描符号 $\mathfrak{S}(r)$ 决定。$q_n, \mathfrak{S}(r)$ 这一对称为“格局”：因此，格局决定了机器可能的行为。在被扫描方格为空白（即不带符号）的某些格局下，机器在被扫描方格上写下一个新符号；在另一些格局下，它擦去被扫描符号。机器也可以改变正在被扫描的方格，但只能向右或向左移动一格。除了这些操作中的任何一种之外，$m$-格局也可以改变。写下的符号中，有一些将构成正在计算的实数的小数数字序列；其余的只是“辅助记忆”的草稿。只有这些草稿才可能被擦除。

It is my contention that these operations include all those which are used in the computation of a number. The defence of this contention will be easier when the theory of the machines is familiar to the reader. In the next section I therefore proceed with the development of the theory and assume that it is understood what is meant by "machine", "tape", "scanned", etc.

我的论点是，这些操作包括了计算一个数时所用的一切操作。等读者熟悉了这种机器的理论，为这一论点辩护就会容易些。因此，我在下一节继续发展这一理论，并假定读者已经明白“机器”“纸带”“被扫描”等的含义。

2. Definitions

2. 定义

Automatic machines

If at each stage the motion of a machine (in the sense of § 1) is completely determined by the configuration, we shall call the machine an "automatic machine" (or $a$-machine).

For some purposes we might use machines (choice machines or $c$-machines) whose motion is only partially determined by the configuration (hence the use of the word "possible" in § 1). When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems. In this paper I deal only with automatic machines, and will therefore often omit the prefix $a$-.

自动机器

如果在每个阶段，机器（第 1 节意义上的）的运动都完全由格局决定，我们就称这台机器为“自动机器”（或 $a$-机器）。

出于某些目的，我们也可以使用运动只部分地由格局决定的机器（选择机器，或 $c$-机器）（因此第 1 节中使用了“可能的”一词）。当这样的机器到达某个这种不确定的格局时，必须等外部操作者作出某种任意选择后才能继续。如果我们用机器来处理公理系统，就会是这种情形。本文只讨论自动机器，因此常常省去前缀 $a$-。

Computing machines

If an $a$-machine prints two kinds of symbols, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine. If the machine is supplied with a blank tape and set in motion, starting from the correct initial $m$-configuration, the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine.

At any stage of the motion of the machine, the number of the scanned square, the complete sequence of all symbols on the tape, and the $m$-configuration will be said to describe the complete configuration at that stage. The changes of the machine and tape between successive complete configurations will be called the moves of the machine.

计算机器

如果一台 $a$-机器打印两类符号，其中第一类（称为数字）完全由 0 和 1 组成（其余的称为第二类符号），这台机器就称为计算机器。如果给机器配上一条空白纸带，从正确的初始 $m$-格局开始让它运转，它所打印的符号中属于第一类的那个子序列，称为机器所计算的序列。在这个序列前面加上小数点，得到一个二进制小数表达式，它所表示的实数称为机器所计算的数。

在机器运动的任一阶段，被扫描方格的编号、纸带上全部符号的完整序列以及 $m$-格局，被说成描述了该阶段的完全格局。机器和纸带在相继的完全格局之间的变化，称为机器的动作（moves）。

Circular and circle-free machines

If a computing machine never writes down more than a finite number of symbols of the first kind, it will be called circular. Otherwise it is said to be circle-free.

A machine will be circular if it reaches a configuration from which there is no possible move, or if it goes on moving, and possibly printing symbols of the second kind, but cannot print any more symbols of the first kind. The significance of the term "circular" will be explained in § 8.

Computable sequences and numbers

A sequence is said to be computable if it can be computed by a circle-free machine. A number is computable if it differs by an integer from the number computed by a circle-free machine.

We shall avoid confusion by speaking more often of computable sequences than of computable numbers.

有环机器与无环机器

如果一台计算机器写下的第一类符号从不超过有限个，就称它为有环的（circular）；否则称它为无环的（circle-free）。

如果机器到达一个无法再作任何动作的格局，或者它继续运动、也许还打印第二类符号，但再也不能打印第一类符号，那么它就是有环的。“有环”一词的含义将在第 8 节解释。

可计算序列与可计算数

如果一个序列能由一台无环机器计算出来，就说它是可计算的。如果一个数与某台无环机器所计算的数相差一个整数，它就是可计算的。

为避免混淆，我们将更多地谈论可计算序列，而不是可计算数。

3. Examples of computing machines

3. 计算机器的例子

I. A machine can be constructed to compute the sequence 010101…. The machine is to have the four $m$-configurations "$\mathfrak{b}$", "$\mathfrak{c}$", "$\mathfrak{f}$", "$\mathfrak{e}$" and is capable of printing "0" and "1". The behaviour of the machine is described in the following table in which "$R$" means "the machine moves so that it scans the square immediately on the right of the one it was scanning previously". Similarly for "$L$". "$E$" means "the scanned symbol is erased" and "$P$" stands for "prints". This table (and all succeeding tables of the same kind) is to be understood to mean that for a configuration described in the first two columns the operations in the third column are carried out successively, and the machine then goes over into the $m$-configuration described in the last column. When the second column is left blank, it is understood that the behaviour of the third and fourth columns applies for any symbol and for no symbol. The machine starts in the $m$-configuration $\mathfrak{b}$ with a blank tape.

m-config.	symbol	operations	final m-config.
$\mathfrak{b}$	None	$P0, R$	$\mathfrak{c}$
$\mathfrak{c}$	None	$R$	$\mathfrak{e}$
$\mathfrak{e}$	None	$P1, R$	$\mathfrak{f}$
$\mathfrak{f}$	None	$R$	$\mathfrak{b}$

(The first two columns are headed "Configuration", the last two "Behaviour".)

I. 可以构造一台机器来计算序列 010101……。这台机器有四个 $m$-格局“$\mathfrak{b}$”“$\mathfrak{c}$”“$\mathfrak{f}$”“$\mathfrak{e}$”，能够打印“0”和“1”。机器的行为由下表描述，表中“$R$”表示“机器移动，使它扫描原先所扫描方格紧右边的方格”，“$L$”类似。“$E$”表示“擦去被扫描符号”，“$P$”表示“打印”。这张表（以及以后所有同类的表）应理解为：对于前两栏所描述的格局，依次执行第三栏中的操作，然后机器转入最后一栏所描述的 $m$-格局。当第二栏空着时，理解为第三、四栏的行为适用于任何符号以及无符号的情形。机器从 $m$-格局 $\mathfrak{b}$ 开始，纸带为空白。

m-格局	符号	操作	最终 m-格局
$\mathfrak{b}$	无	$P0, R$	$\mathfrak{c}$
$\mathfrak{c}$	无	$R$	$\mathfrak{e}$
$\mathfrak{e}$	无	$P1, R$	$\mathfrak{f}$
$\mathfrak{f}$	无	$R$	$\mathfrak{b}$

（前两栏总标题为“格局”，后两栏为“行为”。）

If (contrary to the description in § 1) we allow the letters $L$, $R$ to appear more than once in the operations column we can simplify the table considerably.

m-config.	symbol	operations	final m-config.
$\mathfrak{b}$	None	$P0$	$\mathfrak{b}$
	0	$R, R, P1$	$\mathfrak{b}$
	1	$R, R, P0$	$\mathfrak{b}$

如果（与第 1 节的描述相反）允许字母 $L$、$R$ 在操作栏中出现不止一次，就可以大大简化这张表。

m-格局	符号	操作	最终 m-格局
$\mathfrak{b}$	无	$P0$	$\mathfrak{b}$
	0	$R, R, P1$	$\mathfrak{b}$
	1	$R, R, P0$	$\mathfrak{b}$

II. As a slightly more difficult example we can construct a machine to compute the sequence 001011011101111011111…. The machine is to be capable of five $m$-configurations, viz. "$\mathfrak{o}$", "$\mathfrak{q}$", "$\mathfrak{p}$", "$\mathfrak{f}$", "$\mathfrak{b}$" and of printing "ə", "$x$", "0", "1". The first three symbols on the tape will be "əə0"; the other figures follow on alternate squares. On the intermediate squares we never print anything but "$x$". These letters serve to "keep the place" for us and are erased when we have finished with them. We also arrange that in the sequence of figures on alternate squares there shall be no blanks.

m-config.	symbol	operations	final m-config.
$\mathfrak{b}$		$P\text{ə}, R, P\text{ə}, R, P0, R, R, P0, L, L$	$\mathfrak{o}$
$\mathfrak{o}$	1	$R, Px, L, L, L$	$\mathfrak{o}$
	0		$\mathfrak{q}$
$\mathfrak{q}$	Any (0 or 1)	$R, R$	$\mathfrak{q}$
	None	$P1, L$	$\mathfrak{p}$
$\mathfrak{p}$	$x$	$E, R$	$\mathfrak{q}$
	ə	$R$	$\mathfrak{f}$
	None	$L, L$	$\mathfrak{p}$
$\mathfrak{f}$	Any	$R, R$	$\mathfrak{f}$
	None	$P0, L, L$	$\mathfrak{o}$

II. 作为稍难一点的例子，我们可以构造一台机器来计算序列 001011011101111011111……。这台机器能处于五个 $m$-格局，即“$\mathfrak{o}$”“$\mathfrak{q}$”“$\mathfrak{p}$”“$\mathfrak{f}$”“$\mathfrak{b}$”，能够打印“ə”“$x$”“0”“1”。纸带上的前三个符号将是“əə0”；其他数字隔一格依次排列。在中间的方格上，我们只打印“$x$”。这些字母为我们“占位”，用完后就擦掉。我们还规定，在隔格排列的数字序列中不留空白。

m-格局	符号	操作	最终 m-格局
$\mathfrak{b}$		$P\text{ə}, R, P\text{ə}, R, P0, R, R, P0, L, L$	$\mathfrak{o}$
$\mathfrak{o}$	1	$R, Px, L, L, L$	$\mathfrak{o}$
	0		$\mathfrak{q}$
$\mathfrak{q}$	任意（0 或 1）	$R, R$	$\mathfrak{q}$
	无	$P1, L$	$\mathfrak{p}$
$\mathfrak{p}$	$x$	$E, R$	$\mathfrak{q}$
	ə	$R$	$\mathfrak{f}$
	无	$L, L$	$\mathfrak{p}$
$\mathfrak{f}$	任意	$R, R$	$\mathfrak{f}$
	无	$P0, L, L$	$\mathfrak{o}$

To illustrate the working of this machine a table is given below of the first few complete configurations. These complete configurations are described by writing down the sequence of symbols which are on the tape, with the $m$-configuration written below the scanned symbol. The successive complete configurations are separated by colons.

 :əə0   0:əə0   0:əə0   0:əə0   0    :əə0   0   1:
 𝔟       𝔬       𝔮              𝔮               𝔭
 əə0   0   1:əə0   0   1:əə0   0   1:əə0   0   1:
         𝔭           𝔭       𝔣                   𝔣
 əə0   0   1:əə0   0   1    :əə0   0   1   0:
             𝔣                    𝔣        𝔬
 əə0   0   1x0:....
         𝔬

This table could also be written in the form

$$\mathfrak{b}:\text{ə}\text{ə}\,\mathfrak{o}0\quad 0:\text{ə}\text{ə}\,\mathfrak{q}0\quad 0:\ldots, \tag{C}$$

in which a space has been made on the left of the scanned symbol and the $m$-configuration written in this space. This form is less easy to follow, but we shall make use of it later for theoretical purposes.

为了说明这台机器如何工作，下面列出最初几个完全格局。描述这些完全格局的方法是：写下纸带上的符号序列，并把 $m$-格局写在被扫描符号的下方。相继的完全格局用冒号隔开。

 :əə0   0:əə0   0:əə0   0:əə0   0    :əə0   0   1:
 𝔟       𝔬       𝔮              𝔮               𝔭
 əə0   0   1:əə0   0   1:əə0   0   1:əə0   0   1:
         𝔭           𝔭       𝔣                   𝔣
 əə0   0   1:əə0   0   1    :əə0   0   1   0:
             𝔣                    𝔣        𝔬
 əə0   0   1x0:....
         𝔬

（译注：$m$-格局字母在原刊中写在被扫描符号正下方；此处用等宽文本近似原排版，对齐位置以原文 PDF 为准。）

这张表也可以写成如下形式

$$\mathfrak{b}:\text{ə}\text{ə}\,\mathfrak{o}0\quad 0:\text{ə}\text{ə}\,\mathfrak{q}0\quad 0:\ldots, \tag{C}$$

即在被扫描符号左边留出一个空位，把 $m$-格局写在这个空位里。这种形式不太容易看懂，但我们以后会为理论目的而使用它。

The convention of writing the figures only on alternate squares is very useful: I shall always make use of it. I shall call the one sequence of alternate squares $F$-squares and the other sequence $E$-squares. The symbols on $E$-squares will be liable to erasure. The symbols on $F$-squares form a continuous sequence. There are no blanks until the end is reached. There is no need to have more than one $E$-square between each pair of $F$-squares: an apparent need of more $E$-squares can be satisfied by having a sufficiently rich variety of symbols capable of being printed on $E$-squares. If a symbol $\beta$ is on an $F$-square $S$ and a symbol $\alpha$ is on the $E$-square next on the right of $S$, then $S$ and $\beta$ will be said to be marked with $\alpha$. The process of printing this $\alpha$ will be called marking $\beta$ (or $S$) with $\alpha$.

只在隔一格的方格上写数字，这一约定非常有用：我将始终采用它。我把隔格方格中的一个序列称为 $F$-方格，另一个序列称为 $E$-方格。$E$-方格上的符号可以被擦除。$F$-方格上的符号构成一个连续序列，直到末尾都没有空白。每两个 $F$-方格之间不需要多于一个 $E$-方格：表面上对更多 $E$-方格的需要，可以通过让能够打印在 $E$-方格上的符号种类足够丰富来满足。如果符号 $\beta$ 在 $F$-方格 $S$ 上，而符号 $\alpha$ 在 $S$ 右边紧邻的 $E$-方格上，就说 $S$ 和 $\beta$ 被 $\alpha$ 标记了。打印这个 $\alpha$ 的过程，称为用 $\alpha$ 标记 $\beta$（或 $S$）。

4. Abbreviated tables

4. 简化表

There are certain types of process used by nearly all machines, and these, in some machines, are used in many connections. These processes include copying down sequences of symbols, comparing sequences, erasing all symbols of a given form, etc. Where such processes are concerned we can abbreviate the tables for the $m$-configurations considerably by the use of "skeleton tables". In skeleton tables there appear capital German letters and small Greek letters. These are of the nature of "variables". By replacing each capital German letter throughout by an $m$-configuration and each small Greek letter by a symbol, we obtain the table for an $m$-configuration.

The skeleton tables are to be regarded as nothing but abbreviations: they are not essential. So long as the reader understands how to obtain the complete tables from the skeleton tables, there is no need to give any exact definitions in this connection.

有几类过程几乎为所有机器所用，在某些机器中还在许多场合使用。这些过程包括抄写符号序列、比较序列、擦去某种形式的全部符号等。凡涉及这类过程时，借助“骨架表”可以大大简化 $m$-格局的表。骨架表中出现大写德文字母和小写希腊字母，它们具有“变量”的性质。把每个大写德文字母处处替换为一个 $m$-格局，把每个小写希腊字母替换为一个符号，就得到某个 $m$-格局的表。

骨架表只应看作缩写，并非必不可少。只要读者明白如何由骨架表得到完整的表，就无需在这方面给出任何精确的定义。

Let us consider an example:

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{f}(\mathfrak{C},\mathfrak{B},\alpha)$	ə	$L$	$\mathfrak{f}_1(\mathfrak{C},\mathfrak{B},\alpha)$
	not ə	$L$	$\mathfrak{f}(\mathfrak{C},\mathfrak{B},\alpha)$
$\mathfrak{f}_1(\mathfrak{C},\mathfrak{B},\alpha)$	$\alpha$		$\mathfrak{C}$
	not $\alpha$	$R$	$\mathfrak{f}_1(\mathfrak{C},\mathfrak{B},\alpha)$
	None	$R$	$\mathfrak{f}_2(\mathfrak{C},\mathfrak{B},\alpha)$
$\mathfrak{f}_2(\mathfrak{C},\mathfrak{B},\alpha)$	$\alpha$		$\mathfrak{C}$
	not $\alpha$	$R$	$\mathfrak{f}_1(\mathfrak{C},\mathfrak{B},\alpha)$
	None	$R$	$\mathfrak{B}$

From the $m$-configuration $\mathfrak{f}(\mathfrak{C},\mathfrak{B},\alpha)$ the machine finds the symbol of form $\alpha$ which is farthest to the left (the "first $\alpha$") and the $m$-configuration then becomes $\mathfrak{C}$. If there is no $\alpha$ then the $m$-configuration becomes $\mathfrak{B}$.

If we were to replace $\mathfrak{C}$ throughout by $\mathfrak{q}$ (say), $\mathfrak{B}$ by $\mathfrak{r}$, and $\alpha$ by $x$, we should have a complete table for the $m$-configuration $\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$. $\mathfrak{f}$ is called an "$m$-configuration function" or "$m$-function".

我们来看一个例子：

m-格局	符号	行为	最终 m-格局
$\mathfrak{f}(\mathfrak{C},\mathfrak{B},\alpha)$	ə	$L$	$\mathfrak{f}_1(\mathfrak{C},\mathfrak{B},\alpha)$
	非 ə	$L$	$\mathfrak{f}(\mathfrak{C},\mathfrak{B},\alpha)$
$\mathfrak{f}_1(\mathfrak{C},\mathfrak{B},\alpha)$	$\alpha$		$\mathfrak{C}$
	非 $\alpha$	$R$	$\mathfrak{f}_1(\mathfrak{C},\mathfrak{B},\alpha)$
	无	$R$	$\mathfrak{f}_2(\mathfrak{C},\mathfrak{B},\alpha)$
$\mathfrak{f}_2(\mathfrak{C},\mathfrak{B},\alpha)$	$\alpha$		$\mathfrak{C}$
	非 $\alpha$	$R$	$\mathfrak{f}_1(\mathfrak{C},\mathfrak{B},\alpha)$
	无	$R$	$\mathfrak{B}$

从 $m$-格局 $\mathfrak{f}(\mathfrak{C},\mathfrak{B},\alpha)$ 出发，机器找到最左边的那个形如 $\alpha$ 的符号（“第一个 $\alpha$”），然后 $m$-格局变为 $\mathfrak{C}$。如果没有 $\alpha$，$m$-格局就变为 $\mathfrak{B}$。

如果把 $\mathfrak{C}$ 处处换成（比如）$\mathfrak{q}$，把 $\mathfrak{B}$ 换成 $\mathfrak{r}$，把 $\alpha$ 换成 $x$，就得到 $m$-格局 $\mathfrak{f}(\mathfrak{q},\mathfrak{r},x)$ 的完整表。$\mathfrak{f}$ 称为“$m$-格局函数”或“$m$-函数”。

The only expressions which are admissible for substitution in an $m$-function are the $m$-configurations and symbols of the machine. These have to be enumerated more or less explicitly: they may include expressions such as $\mathfrak{p}(\mathfrak{e}, x)$; indeed they must if there are any $m$-functions used at all. If we did not insist on this explicit enumeration, but simply stated that the machine had certain $m$-configurations (enumerated) and all $m$-configurations obtainable by substitution of $m$-configurations in certain $m$-functions, we should usually get an infinity of $m$-configurations; e.g., we might say that the machine was to have the $m$-configuration $\mathfrak{q}$ and all $m$-configurations obtainable by substituting an $m$-configuration for $\mathfrak{C}$ in $\mathfrak{p}(\mathfrak{C})$. Then it would have $\mathfrak{q}$, $\mathfrak{p}(\mathfrak{q})$, $\mathfrak{p}(\mathfrak{p}(\mathfrak{q}))$, $\mathfrak{p}(\mathfrak{p}(\mathfrak{p}(\mathfrak{q})))$, … as $m$-configurations.

Our interpretation rule then is this. We are given the names of the $m$-configurations of the machine, mostly expressed in terms of $m$-functions. We are also given skeleton tables. All we want is the complete table for the $m$-configurations of the machine. This is obtained by repeated substitution in the skeleton tables.

可以代入 $m$-函数的表达式，只有机器的 $m$-格局和符号。这些必须或多或少明确地列举出来：其中可以包括像 $\mathfrak{p}(\mathfrak{e}, x)$ 这样的表达式；事实上，只要用到了 $m$-函数，就必须包括。如果我们不坚持这种明确的列举，而只是说明机器具有某些（列举出的）$m$-格局，以及在某些 $m$-函数中代入 $m$-格局所能得到的一切 $m$-格局，那么通常会得到无穷多个 $m$-格局；例如，我们可以说机器具有 $m$-格局 $\mathfrak{q}$，以及在 $\mathfrak{p}(\mathfrak{C})$ 中用 $m$-格局代替 $\mathfrak{C}$ 所能得到的一切 $m$-格局。这样它就会以 $\mathfrak{q}$、$\mathfrak{p}(\mathfrak{q})$、$\mathfrak{p}(\mathfrak{p}(\mathfrak{q}))$、$\mathfrak{p}(\mathfrak{p}(\mathfrak{p}(\mathfrak{q})))$……为 $m$-格局。

于是我们的解释规则是：给定机器各 $m$-格局的名称，它们大多用 $m$-函数来表示；也给定骨架表。我们要的只是机器各 $m$-格局的完整表，这可以通过在骨架表中反复代入得到。

Further examples

(In the explanations the symbol "→" is used to signify "the machine goes into the $m$-configuration. . . .")

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{e}(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{f}(\mathfrak{e}_1(\mathfrak{C},\mathfrak{B},\alpha),\mathfrak{B},\alpha)$
$\mathfrak{e}_1(\mathfrak{C},\mathfrak{B},\alpha)$		$E$	$\mathfrak{C}$

From $\mathfrak{e}(\mathfrak{C},\mathfrak{B},\alpha)$ the first $\alpha$ is erased and → $\mathfrak{C}$. If there is no $\alpha$ → $\mathfrak{B}$.

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{e}(\mathfrak{B},\alpha)$			$\mathfrak{e}(\mathfrak{e}(\mathfrak{B},\alpha),\mathfrak{B},\alpha)$

From $\mathfrak{e}(\mathfrak{B},\alpha)$ all letters $\alpha$ are erased and → $\mathfrak{B}$.

更多的例子

（在说明中，符号“→”表示“机器转入 $m$-格局……”。）

m-格局	符号	行为	最终 m-格局
$\mathfrak{e}(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{f}(\mathfrak{e}_1(\mathfrak{C},\mathfrak{B},\alpha),\mathfrak{B},\alpha)$
$\mathfrak{e}_1(\mathfrak{C},\mathfrak{B},\alpha)$		$E$	$\mathfrak{C}$

从 $\mathfrak{e}(\mathfrak{C},\mathfrak{B},\alpha)$ 出发，擦去第一个 $\alpha$，并 → $\mathfrak{C}$。如果没有 $\alpha$，→ $\mathfrak{B}$。

m-格局	符号	行为	最终 m-格局
$\mathfrak{e}(\mathfrak{B},\alpha)$			$\mathfrak{e}(\mathfrak{e}(\mathfrak{B},\alpha),\mathfrak{B},\alpha)$

从 $\mathfrak{e}(\mathfrak{B},\alpha)$ 出发，擦去所有字母 $\alpha$，并 → $\mathfrak{B}$。

The last example seems somewhat more difficult to interpret than most. Let us suppose that in the list of $m$-configurations of some machine there appears $\mathfrak{e}(\mathfrak{b}, x)$ $(= \mathfrak{q}$, say$)$. The table is

$\mathfrak{e}(\mathfrak{b},x)$	$\mathfrak{e}(\mathfrak{e}(\mathfrak{b},x),\mathfrak{b},x)$

or

$\mathfrak{q}$	$\mathfrak{e}(\mathfrak{q},\mathfrak{b},x)$.

Or, in greater detail:

$\mathfrak{q}$		$\mathfrak{e}(\mathfrak{q},\mathfrak{b},x)$
$\mathfrak{e}(\mathfrak{q},\mathfrak{b},x)$		$\mathfrak{f}(\mathfrak{e}_1(\mathfrak{q},\mathfrak{b},x),\mathfrak{b},x)$
$\mathfrak{e}_1(\mathfrak{q},\mathfrak{b},x)$	$E$	$\mathfrak{q}$.

In this we could replace $\mathfrak{e}_1(\mathfrak{q},\mathfrak{b},x)$ by $\mathfrak{q}'$ and then give the table for $\mathfrak{f}$ (with the right substitutions) and eventually reach a table in which no $m$-functions appeared.

最后一个例子似乎比大多数例子更难理解。假设在某台机器的 $m$-格局列表中出现了 $\mathfrak{e}(\mathfrak{b}, x)$（比如记为 $\mathfrak{q}$）。其表为

$\mathfrak{e}(\mathfrak{b},x)$	$\mathfrak{e}(\mathfrak{e}(\mathfrak{b},x),\mathfrak{b},x)$

或

$\mathfrak{q}$	$\mathfrak{e}(\mathfrak{q},\mathfrak{b},x)$。

或者更详细地：

$\mathfrak{q}$		$\mathfrak{e}(\mathfrak{q},\mathfrak{b},x)$
$\mathfrak{e}(\mathfrak{q},\mathfrak{b},x)$		$\mathfrak{f}(\mathfrak{e}_1(\mathfrak{q},\mathfrak{b},x),\mathfrak{b},x)$
$\mathfrak{e}_1(\mathfrak{q},\mathfrak{b},x)$	$E$	$\mathfrak{q}$。

在这里，我们可以把 $\mathfrak{e}_1(\mathfrak{q},\mathfrak{b},x)$ 换成 $\mathfrak{q}'$，然后给出 $\mathfrak{f}$ 的表（作适当的代入），最终得到一张不出现任何 $m$-函数的表。

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{pe}(\mathfrak{C},\beta)$			$\mathfrak{f}(\mathfrak{pe}_1(\mathfrak{C},\beta),\mathfrak{C},\text{ə})$
$\mathfrak{pe}_1(\mathfrak{C},\beta)$	Any	$R, R$	$\mathfrak{pe}_1(\mathfrak{C},\beta)$
	None	$P\beta$	$\mathfrak{C}$

From $\mathfrak{pe}(\mathfrak{C},\beta)$ the machine prints $\beta$ at the end of the sequence of symbols and → $\mathfrak{C}$.

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{l}(\mathfrak{C})$		$L$	$\mathfrak{C}$
$\mathfrak{r}(\mathfrak{C})$		$R$	$\mathfrak{C}$
$\mathfrak{f}'(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{f}(\mathfrak{l}(\mathfrak{C}),\mathfrak{B},\alpha)$
$\mathfrak{f}''(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{f}(\mathfrak{r}(\mathfrak{C}),\mathfrak{B},\alpha)$

From $\mathfrak{f}'(\mathfrak{C},\mathfrak{B},\alpha)$ it does the same as for $\mathfrak{f}(\mathfrak{C},\mathfrak{B},\alpha)$ but moves to the left before → $\mathfrak{C}$.

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{c}(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{f}'(\mathfrak{c}_1(\mathfrak{C}),\mathfrak{B},\alpha)$
$\mathfrak{c}_1(\mathfrak{C})$	$\beta$		$\mathfrak{pe}(\mathfrak{C},\beta)$

$\mathfrak{c}(\mathfrak{C},\mathfrak{B},\alpha)$. The machine writes at the end the first symbol marked $\alpha$ and → $\mathfrak{C}$.

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

m-格局	符号	行为	最终 m-格局
$\mathfrak{pe}(\mathfrak{C},\beta)$			$\mathfrak{f}(\mathfrak{pe}_1(\mathfrak{C},\beta),\mathfrak{C},\text{ə})$
$\mathfrak{pe}_1(\mathfrak{C},\beta)$	任意	$R, R$	$\mathfrak{pe}_1(\mathfrak{C},\beta)$
	无	$P\beta$	$\mathfrak{C}$

从 $\mathfrak{pe}(\mathfrak{C},\beta)$ 出发，机器在符号序列的末尾打印 $\beta$，并 → $\mathfrak{C}$。

m-格局	符号	行为	最终 m-格局
$\mathfrak{l}(\mathfrak{C})$		$L$	$\mathfrak{C}$
$\mathfrak{r}(\mathfrak{C})$		$R$	$\mathfrak{C}$
$\mathfrak{f}'(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{f}(\mathfrak{l}(\mathfrak{C}),\mathfrak{B},\alpha)$
$\mathfrak{f}''(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{f}(\mathfrak{r}(\mathfrak{C}),\mathfrak{B},\alpha)$

从 $\mathfrak{f}'(\mathfrak{C},\mathfrak{B},\alpha)$ 出发，机器所做的与 $\mathfrak{f}(\mathfrak{C},\mathfrak{B},\alpha)$ 相同，只是在 → $\mathfrak{C}$ 之前先向左移动一格。

m-格局	符号	行为	最终 m-格局
$\mathfrak{c}(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{f}'(\mathfrak{c}_1(\mathfrak{C}),\mathfrak{B},\alpha)$
$\mathfrak{c}_1(\mathfrak{C})$	$\beta$		$\mathfrak{pe}(\mathfrak{C},\beta)$

$\mathfrak{c}(\mathfrak{C},\mathfrak{B},\alpha)$：机器在末尾写下第一个被标记为 $\alpha$ 的符号，并 → $\mathfrak{C}$。

最后一行代表这样一组行的全体：把其中的 $\beta$ 换成所涉机器纸带上可能出现的任何符号所得到的所有行。

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{ce}(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{c}(\mathfrak{e}(\mathfrak{C},\mathfrak{B},\alpha),\mathfrak{B},\alpha)$
$\mathfrak{ce}(\mathfrak{B},\alpha)$			$\mathfrak{ce}(\mathfrak{ce}(\mathfrak{B},\alpha),\mathfrak{B},\alpha)$

$\mathfrak{ce}(\mathfrak{B},\alpha)$. The machine copies down in order at the end all symbols marked $\alpha$ and erases the letters $\alpha$; → $\mathfrak{B}$.

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{re}(\mathfrak{C},\mathfrak{B},\alpha,\beta)$			$\mathfrak{f}(\mathfrak{re}_1(\mathfrak{C},\mathfrak{B},\alpha,\beta),\mathfrak{B},\alpha)$
$\mathfrak{re}_1(\mathfrak{C},\mathfrak{B},\alpha,\beta)$		$E, P\beta$	$\mathfrak{C}$
$\mathfrak{re}(\mathfrak{B},\alpha,\beta)$			$\mathfrak{re}(\mathfrak{re}(\mathfrak{B},\alpha,\beta),\mathfrak{B},\alpha,\beta)$

$\mathfrak{re}(\mathfrak{C},\mathfrak{B},\alpha,\beta)$. The machine replaces the first $\alpha$ by $\beta$ and → $\mathfrak{C}$ → $\mathfrak{B}$ if there is no $\alpha$.

$\mathfrak{re}(\mathfrak{B},\alpha,\beta)$. The machine replaces all letters $\alpha$ by $\beta$; → $\mathfrak{B}$.

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{cr}(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{c}(\mathfrak{re}(\mathfrak{C},\mathfrak{B},\alpha,\alpha),\mathfrak{B},\alpha)$
$\mathfrak{cr}(\mathfrak{B},\alpha)$			$\mathfrak{cr}(\mathfrak{cr}(\mathfrak{B},\alpha),\mathfrak{re}(\mathfrak{B},\alpha,\alpha),\alpha)$

$\mathfrak{cr}(\mathfrak{B},\alpha)$ differs from $\mathfrak{ce}(\mathfrak{B},\alpha)$ only in that the letters $\alpha$ are not erased. The $m$-configuration $\mathfrak{cr}(\mathfrak{B},\alpha)$ is taken up when no letters "$\alpha$" are on the tape.

m-格局	符号	行为	最终 m-格局
$\mathfrak{ce}(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{c}(\mathfrak{e}(\mathfrak{C},\mathfrak{B},\alpha),\mathfrak{B},\alpha)$
$\mathfrak{ce}(\mathfrak{B},\alpha)$			$\mathfrak{ce}(\mathfrak{ce}(\mathfrak{B},\alpha),\mathfrak{B},\alpha)$

$\mathfrak{ce}(\mathfrak{B},\alpha)$：机器按顺序在末尾抄下所有被标记为 $\alpha$ 的符号，并擦去字母 $\alpha$；→ $\mathfrak{B}$。

m-格局	符号	行为	最终 m-格局
$\mathfrak{re}(\mathfrak{C},\mathfrak{B},\alpha,\beta)$			$\mathfrak{f}(\mathfrak{re}_1(\mathfrak{C},\mathfrak{B},\alpha,\beta),\mathfrak{B},\alpha)$
$\mathfrak{re}_1(\mathfrak{C},\mathfrak{B},\alpha,\beta)$		$E, P\beta$	$\mathfrak{C}$
$\mathfrak{re}(\mathfrak{B},\alpha,\beta)$			$\mathfrak{re}(\mathfrak{re}(\mathfrak{B},\alpha,\beta),\mathfrak{B},\alpha,\beta)$

$\mathfrak{re}(\mathfrak{C},\mathfrak{B},\alpha,\beta)$：机器把第一个 $\alpha$ 换成 $\beta$，并 → $\mathfrak{C}$；如果没有 $\alpha$，→ $\mathfrak{B}$。

$\mathfrak{re}(\mathfrak{B},\alpha,\beta)$：机器把所有字母 $\alpha$ 换成 $\beta$；→ $\mathfrak{B}$。

m-格局	符号	行为	最终 m-格局
$\mathfrak{cr}(\mathfrak{C},\mathfrak{B},\alpha)$			$\mathfrak{c}(\mathfrak{re}(\mathfrak{C},\mathfrak{B},\alpha,\alpha),\mathfrak{B},\alpha)$
$\mathfrak{cr}(\mathfrak{B},\alpha)$			$\mathfrak{cr}(\mathfrak{cr}(\mathfrak{B},\alpha),\mathfrak{re}(\mathfrak{B},\alpha,\alpha),\alpha)$

$\mathfrak{cr}(\mathfrak{B},\alpha)$ 与 $\mathfrak{ce}(\mathfrak{B},\alpha)$ 的唯一区别在于不擦去字母 $\alpha$。当纸带上没有字母“$\alpha$”时，进入 $m$-格局 $\mathfrak{cr}(\mathfrak{B},\alpha)$。

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{cp}(\mathfrak{C},\mathfrak{A},\mathfrak{E},\alpha,\beta)$			$\mathfrak{f}'(\mathfrak{cp}_1(\mathfrak{C}_1\mathfrak{A},\beta),\mathfrak{f}(\mathfrak{A},\mathfrak{E},\beta),\alpha)$
$\mathfrak{cp}_1(\mathfrak{C},\mathfrak{A},\beta)$	$\gamma$		$\mathfrak{f}'(\mathfrak{cp}_2(\mathfrak{C},\mathfrak{A},\gamma),\mathfrak{A},\beta)$
$\mathfrak{cp}_2(\mathfrak{C},\mathfrak{A},\gamma)$	$\gamma$		$\mathfrak{C}$
	not $\gamma$		$\mathfrak{A}$.

The first symbol marked $\alpha$ and the first marked $\beta$ are compared. If there is neither $\alpha$ nor $\beta$, → $\mathfrak{E}$. If there are both and the symbols are alike, → $\mathfrak{C}$. Otherwise → $\mathfrak{A}$.

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{cpe}(\mathfrak{C},\mathfrak{A},\mathfrak{E},\alpha,\beta)$			$\mathfrak{cp}(\mathfrak{e}(\mathfrak{e}(\mathfrak{C},\mathfrak{C},\beta),\mathfrak{C},\alpha),\mathfrak{A},\mathfrak{E},\alpha,\beta)$

$\mathfrak{cpe}(\mathfrak{C},\mathfrak{A},\mathfrak{E},\alpha,\beta)$ differs from $\mathfrak{cp}(\mathfrak{C},\mathfrak{A},\mathfrak{E},\alpha,\beta)$ in that in the case when there is similarity the first $\alpha$ and $\beta$ are erased.

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{cpe}(\mathfrak{A},\mathfrak{E},\alpha,\beta)$			$\mathfrak{cpe}(\mathfrak{cpe}(\mathfrak{A},\mathfrak{E},\alpha,\beta),\mathfrak{A},\mathfrak{E},\alpha,\beta)$.

$\mathfrak{cpe}(\mathfrak{A},\mathfrak{E},\alpha,\beta)$. The sequence of symbols marked $\alpha$ is compared with the sequence marked $\beta$. → $\mathfrak{E}$ if they are similar. Otherwise → $\mathfrak{A}$. Some of the symbols $\alpha$ and $\beta$ are erased.

m-格局	符号	行为	最终 m-格局
$\mathfrak{cp}(\mathfrak{C},\mathfrak{A},\mathfrak{E},\alpha,\beta)$			$\mathfrak{f}'(\mathfrak{cp}_1(\mathfrak{C}_1\mathfrak{A},\beta),\mathfrak{f}(\mathfrak{A},\mathfrak{E},\beta),\alpha)$
$\mathfrak{cp}_1(\mathfrak{C},\mathfrak{A},\beta)$	$\gamma$		$\mathfrak{f}'(\mathfrak{cp}_2(\mathfrak{C},\mathfrak{A},\gamma),\mathfrak{A},\beta)$
$\mathfrak{cp}_2(\mathfrak{C},\mathfrak{A},\gamma)$	$\gamma$		$\mathfrak{C}$
	非 $\gamma$		$\mathfrak{A}$。

（译注：第一行中的 $\mathfrak{cp}_1(\mathfrak{C}_1\mathfrak{A},\beta)$ 按原刊照录，按上下文应为 $\mathfrak{cp}_1(\mathfrak{C},\mathfrak{A},\beta)$。）

比较第一个被标记为 $\alpha$ 的符号与第一个被标记为 $\beta$ 的符号。如果既没有 $\alpha$ 也没有 $\beta$，→ $\mathfrak{E}$。如果两者都有且符号相同，→ $\mathfrak{C}$。否则 → $\mathfrak{A}$。

m-格局	符号	行为	最终 m-格局
$\mathfrak{cpe}(\mathfrak{C},\mathfrak{A},\mathfrak{E},\alpha,\beta)$			$\mathfrak{cp}(\mathfrak{e}(\mathfrak{e}(\mathfrak{C},\mathfrak{C},\beta),\mathfrak{C},\alpha),\mathfrak{A},\mathfrak{E},\alpha,\beta)$

$\mathfrak{cpe}(\mathfrak{C},\mathfrak{A},\mathfrak{E},\alpha,\beta)$ 与 $\mathfrak{cp}(\mathfrak{C},\mathfrak{A},\mathfrak{E},\alpha,\beta)$ 的区别在于：在相同的情形下，第一个 $\alpha$ 和第一个 $\beta$ 被擦去。

m-格局	符号	行为	最终 m-格局
$\mathfrak{cpe}(\mathfrak{A},\mathfrak{E},\alpha,\beta)$			$\mathfrak{cpe}(\mathfrak{cpe}(\mathfrak{A},\mathfrak{E},\alpha,\beta),\mathfrak{A},\mathfrak{E},\alpha,\beta)$。

$\mathfrak{cpe}(\mathfrak{A},\mathfrak{E},\alpha,\beta)$：把被标记为 $\alpha$ 的符号序列与被标记为 $\beta$ 的序列相比较。如果两者相同，→ $\mathfrak{E}$；否则 → $\mathfrak{A}$。部分符号 $\alpha$ 和 $\beta$ 被擦去。

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{q}(\mathfrak{C})$	Any	$R$	$\mathfrak{q}(\mathfrak{C})$
	None	$R$	$\mathfrak{q}_1(\mathfrak{C})$
$\mathfrak{q}_1(\mathfrak{C})$	Any	$R$	$\mathfrak{q}(\mathfrak{C})$
	None		$\mathfrak{C}$
$\mathfrak{q}(\mathfrak{C},\alpha)$			$\mathfrak{q}(\mathfrak{q}_1(\mathfrak{C},\alpha))$
$\mathfrak{q}_1(\mathfrak{C},\alpha)$	$\alpha$		$\mathfrak{C}$
	not $\alpha$	$L$	$\mathfrak{q}_1(\mathfrak{C},\alpha)$

$\mathfrak{q}(\mathfrak{C},\alpha)$. The machine finds the last symbol of form $\alpha$. → $\mathfrak{C}$.

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{pe}_2(\mathfrak{C},\alpha,\beta)$			$\mathfrak{pe}(\mathfrak{pe}(\mathfrak{C},\beta),\alpha)$

$\mathfrak{pe}_2(\mathfrak{C},\alpha,\beta)$. The machine prints $\alpha\,\beta$ at the end.

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{ce}_2(\mathfrak{B},\alpha,\beta)$			$\mathfrak{ce}(\mathfrak{ce}(\mathfrak{B},\beta),\alpha)$
$\mathfrak{ce}_3(\mathfrak{B},\alpha,\beta,\gamma)$			$\mathfrak{ce}(\mathfrak{ce}_2(\mathfrak{B},\beta,\gamma),\alpha)$

$\mathfrak{ce}_3(\mathfrak{B},\alpha,\beta,\gamma)$. The machine copies down at the end first the symbols marked $\alpha$, then those marked $\beta$, and finally those marked $\gamma$; it erases the symbols $\alpha$, $\beta$, $\gamma$.

m-config.	Symbol	Behaviour	Final m-config.
$\mathfrak{e}(\mathfrak{C})$	ə	$R$	$\mathfrak{e}_1(\mathfrak{C})$
	Not ə	$L$	$\mathfrak{e}(\mathfrak{C})$
$\mathfrak{e}_1(\mathfrak{C})$	Any	$R, E, R$	$\mathfrak{e}_1(\mathfrak{C})$
	None		$\mathfrak{C}$

From $\mathfrak{e}(\mathfrak{C})$ the marks are erased from all marked symbols. → $\mathfrak{C}$.