图灵在这章论述图灵机的编码，提示图灵机枚举的层次性。

5. 可计算序列的枚举

一个可计算序列 y是由计算y的机器的描述所确定的。因此，序列001011011101111…是由第234页的表所确定的。事实上，任何可计算序列都可以通过这样的表来描述。

把这些表转换成一种标准形式是有用的。首先，我们假设仍以第233页例1中的形式给出的表，也就是说，操作列的条目总是下列形式之一：E : E,R :E,L :Pa: Pa, R: Pa, L:R:L，或没有任何条目。

通过引入更多的m-格局，表总是可以被表达成这种形式。现在我们给这些m-格局编号，正如 §1中分别把它们称作q1, ..., qR。初始格局m-格局总是 q1。我们也为符号S1,....., Sm编号，特别是，空= S0, 0 = S1，1 = S2。

M格局符号 操作 最终格局

qiSjPSk,Lqm(N1)

qiSjPSk,Rqm(N2)

qiSjPSk        qm(N3)

通过这种方式，我们可以把表的每一行都简化为 (Nj, (N2),  (N3)中的一种。

对于形式为(N1)的每行，表达为qiSjSkLqm；(N2)的每行，表达为qiSjSkRqm；(N3)的每行，表达为qiSjSkNqm。

我们把机器表中这样形成的表达式写下来，并用分号隔开。这样我们就得到机器的完整描述了。

在下面的描述中，我们将用D和后面i个字母A来代替qi，用D和后面j个字母C来代替Sj。

这种新的机器描述称为“标准描述（S.D）”。它完全是由字母A, C, D, L, R, N和“；”组成。

如果最后用1代替A，2代替C，3代替D，4代替L，5代替R，6代替N，7代替“；”，我们就得阿拉伯数字形式的机器描述。

由这些数字表示的整数可以称作机器的“描述数（D.N）”。D.N唯一决定了S.D和机器的结构。描述数是n的机器可以记为M(n)。

每个可计算序列至少对应一个描述数，但不存在一个描述数对应多个可计算序列。因此，可计算序列和数是可数的。

我们来生成§ 3中机器I的描述数。重新命名m-格局后，表变成：

q1S0PS1, Rq2

q2S0PS0, Rq3

q3S0PS2, Rq4

q4S0PS0, Rq1

通过增加如下无关的行可以得到其他表：

q1 S1 PS1,R q2

标准形式如下：

q1S0PS1Rq2;q2S0PS0Rq3; q3S0PS2Rq4;q4S0PS0Rq1。

标准描述为：

DADDCRDAA;DAADDEDAAA;DAAADDCCRDAAAA;DAAADDRDA;

一个描述数为：

31332531173113353111731113322531111731111335317

另一个描述数为：

3133253117311335311173111332253111173111133531731323253117

circle-free机器的描述数（D.N）称作满足（satisfactory）数。在§ 8将指出不存在一个通用过程来判定一个给定的数是否是满足数。

5. Enumeration of computable sequences

A computable sequence y is determined by a description of a machine which computes y. Thus the sequence 001011011101111... is determined by the table on p. 234, and, in fact, any computable sequence is capable of being described in terms of such a table.

It will be useful to put these tables into a kind of standard form. In the first place let us suppose that the table is given in the same form as the first table, for example, I on p. 233. That is to say, that the entry in the operations column is always of one of the forms E :E,R:E,L:Pa: Pa, R: Pa, L:R:L: or no entry at all. 

The table can always be put into this form by introducing more m-configurations. Now let us give numbers to the w-configurations, calling them q1, ..., qR, as in §1. The initial m-configuration is always to be called q1. We also give numbers to the symbols S1,....., Sm and, in particular, blank = S0, 0 = S1 1 = S2.

M-config. Symbol Operations Fianl m-config.

qiSj PSk,Lqm(N1)

qiSjPSk,Rqm(N2)

qiSjPSk        qm(N3)

In this way we reduce each line of the table to a line of one of the forms (Nj, (N2),  (N3).

From each line of form (N1) let us form an expression qiSjSkLqm; from each line of form (N2) we form an expression qiSjSkRqm; and from each line of form (N3) we form an expression qiSjSkNqm.

Let us write down all expressions so formed from the table for the machine and separate them by semi-colons. In this way we obtain a complete description of the machine.

In this description we shall replace qi by the letter "D" followed by the letter "A" repeated i times, and $j by "D" followed by "C" repeated j times. 

This new description of the machine may be called the standard description (S.D). It is made up entirely from the letters "A", " C", "D", "L", "R", "N", and from“；”。

If finally we replace "A" by "1", "C" by "2", "D" by "3"," L" c 3> ￡<

by"4","R" by '5","N" by « 6",and « ; » by 7 we shall have a description of the machine in the form of an arabic numeral. 

The integer represented by this numeral may be called a description number (D.N) of the machine. The D.N determine the S.D and the structure of the machine uniquely. The machine whose D.N is n may be described as M(n)。

To each computable sequence there corresponds at least one description number, while to no description number does there correspond more than one computable sequence. The computable sequences and numbers are therefore enumerable.

Let us find a description number for the machine I of § 3. rename the m-configurations its table becomes:

q1S0PS1, Rq2

q2S0PS0, Rq3

q3S0PS2, Rq4

q4S0PS0, Rq1

Other tables could be obtained by adding irrelevant lines such as:

q1 S1 PS1，R q2

Our first standard form would be

q1S0PS1Rq2;q2S0PS0Rq3; q3S0PS2Rq4;q4S0PS0Rq1。

The standard description is

DADDCRDAA;DAADDEDAAA;DAAADDCCRDAAAA;DAAADDRDA;

A description number is 

31332531173113353111731113322531111731111335317

and so is

3133253117311335311173111332253111173111133531731323253117

A number which is a description number of a circle-free machine will be called a satisfactory number. In § 8 it is shown that there can be no general process for determining whether a given number is satisfactory or not.

参考文献：

- Charles Petzold, The Annotated Turing, 2008.

- 图灵的秘密 - 他的生平，思想及论文解读。杨卫东 朱皓等译，2012.