图灵在这章论述图灵机的编码，提示 图灵机枚举的层次性 。 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 格局 符号 操作 最终格局 qi Sj PSk,L qm (N1) qi Sj PSk,R qm (N2) qi Sj PSk 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- 格局后，表变成： q1 S0 PS1, R q2 q2 S0 PS0, R q3 q3 S0 PS2, R q4 q4 S0 PS0, R q1 通过增加如下无关的行可以得到其他表： q1 S1 PS1,R q2 标准形式如下： q1S0PS1Rq2;q2S0PS0Rq3; q3 S0PS2Rq4;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. qi Sj PSk,L qm (N1) qi Sj PSk,R qm (N2) qi Sj PSk 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 ￡ by4,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: q1 S0 PS1, R q2 q2 S0 PS0, R q3 q3 S0 PS2, R q4 q4 S0 PS0, R q1 Other tables could be obtained by adding irrelevant lines such as: q1 S1 PS1 ， R q2 Our first standard form would be q1S0PS1Rq2;q2S0PS0Rq3; q3 S0PS2Rq4;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.
标签: 图灵1926年论文
