# 图灵文章《论可计算数及其在判定问题上的应用》的第5章译文

5. 可计算序列的枚举

M格局符号 操作 最终格局

qiSjPSk,Lqm(N1)

qiSjPSk,Rqm(N2)

qiSjPSk        qm(N3)

q1S0PS1, Rq2

q2S0PS0, Rq3

q3S0PS2, Rq4

q4S0PS0, Rq1

q1 S1 PS1,R q2

q1S0PS1Rq2;q2S0PS0Rq3; q3S0PS2Rq4;q4S0PS0Rq1

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 PS1R q2

Our first standard form would be

q1S0PS1Rq2;q2S0PS0Rq3; q3S0PS2Rq4;q4S0PS0Rq1

The standard description is

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.

http://blog.sciencenet.cn/blog-2322490-1244261.html

## 全部精选博文导读

GMT+8, 2020-9-22 16:30