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

9.    可计算数的范围

1. 直接求助于直觉。

2. 证明两个定义等价（如果新的定义具有更大的直觉吸引力）。

3. 举出大量可计算数的例子。

I. [类型 (a)] 这个论证只是对§1的观点的详细阐述

(a) 改变一个被观察方格的符号；

(b) 将一个被观察方格移动到与前一个被观察方格距离L以内的位置上；

A. 符号的可能变化（a）以及心智的可能变化一起。

B. 观察到的方块的可能变化（b）以及心智的可能变化。

II. [类型(b)]

α是一个序列，我们用Gα(x)表示“α的第x个数字是1”的命题，因此-Gα(x)表示“α的第x个数字是0”。进一步假设我们可以找到一组定义序列α的属性，并且可以用Gα(x)和命题函数N(x)F(x,y)来表达这些性质，其中，N(x)表示“x是一个非负整数F(x,y)表示 y = x +1。用合取符号把这些公式连接起来，我们可以得到一个定义α的公式，将其命名为UU的项中必须包含皮亚诺公理的必要条件，也就是：

(Ǝu) N (u)& (x)(N(x)(Ǝy)F(x,y)) & ( F(x,y)N(y) ),

U & F(n) Gα(u(n)),(An)

U & F(n) ( –Gα(u(n))),(Bn)

III. 这可以被看作是对I的修改，也可以看作是对II的推论

9.    The extent of the computable numbers.

No attempt has yet been made to show that the “computable” numbers include all numbers which would naturally be regarded as computable. All arguments which can be given are bound to be, fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically. The real question at issue is “What are the possible processes which can be carried out in computing a number?”

The arguments which I shall use are of three kinds.

1. A direct appeal to intuition.

2. A proof of the equivalence of two definitions (in case the new definition has a greater intuitive appeal).

3. Giving examples of large classes of numbers which are computable.

Once it is granted that computable numbers are all “computable” several other propositions of the same character follow. In particular, it follows that, if there is a general process for determining whether a formula of the Hilbert function calculus is provable, then the determination can be carried out by a machine.

I. [Type (a)]. This argument is only an elaboration of the ideas of §1.

Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent.[6] The effect of this restriction of the number of symbols is not very serious. It is always possible to use sequences of symbols in the place of single symbols. Thus an Arabic numeral such as {250} 17 or 999999999999999 is normally treated as a single symbol. Similarly in any European language words are treated as single symbols (Chinese, however, attempts to have an enumerable infinity of symbols). The differences from our point of view between the single and compound symbols is that the compound symbols, if they are too lengthy, cannot be observed at one glance. This is in accordance with experience. We cannot tell at a glance whether 9999999999999999 and 999999999999999 are the same.

The behaviour of the computer at any moment is determined by the symbols which he is observing. and his “state of mind” at that moment. We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need be taken into account is finite. The reasons for this are of the same character as those which restrict the number of symbols. If we admitted an infinity of states of mind, some of them will be “arbitrarily close” and will be confused. Again, the restriction is not one which seriously affects computation, since the use of more complicated states of mind can be avoided by writing more symbols on the tape.

Let us imagine the operations performed by the computer to be split up into “simple operations” which are so elementary that it is not easy to imagine them further divided. Every such operation consists of some change of the physical system consisting of the computer and his tape. We know the state of the system if we know the sequence of symbols on the tape, which of these are observed by the computer (possibly with a special order), and the state of mind of the computer. We may suppose that in a simple operation not more than one symbol is altered. Any other changes can be set up into simple changes of this kind. The situation in regard to the squares whose symbols may be altered in this way is the same as in regard to the observed squares. We may, therefore, without loss of generality, assume that the squares whose symbols are changed are always “observed” squares.

Besides these changes of symbols, the simple operations must include changes of distribution of observed squares. The new observed squares must be immediately recognisable by the computer. I think it is reasonable to suppose that they can only be squares whose distance from the closest of the immediately previously observed squares does not exceed a certain fixed amount. Let us say that each of the new observed squares is within L squares of an immediately previously observed square.

In connection with “immediate recognisability”, it may be thought that there are other kinds of square which are immediately recognisable. In particular, squares marked by special symbols might be taken as immediately recognisable. Now if these squares are marked only by single symbols there can be only a finite number of them, and we should not upset our theory by adjoining these marked squares to the observed squares. If, on the other hand, they are marked by a sequence of symbols, we cannot regard the process of recognition as a simple process. This is a fundamental point and should be illustrated. In most mathematical papers the equations and theorems are numbered. Normally the numbers do not go beyond (say) 1000. It is, therefore, possible to recognise a theorem at a glance by its number. But if the paper was very long, we might reach Theorem 157767733443477; then, farther on in the paper, we might find “... hence (applying Theorem 157767733443477) we have...”. In order to make sure which was the relevant theorem we should have to compare the two numbers figure by figure, possibly ticking the figures off in pencil to make sure of their not being counted twice. If in spite of this it is still thought that there are other “immediately recognisable” squares, it does not upset my contention so long as these squares can be found by some process of which my type of machine is capable. This idea is developed in III below.

The simple operations must therefore include:

(a) Changes of the symbol on one of the observed squares.

(b) Changes of one of the squares observed to another square within L squares of one of the previously observed squares.

It may be that some of these changes necessarily involve a change of state of mind. The most general single operation must therefore be taken to be one of the following:

1. A possible change (a) of symbol together with a possible change of state of mind.

B. A possible change (b) of observed squares, together with a possible change of state of mind.

The operation actually performed is determined, as has been suggested on p.250, by the state of mind of the computer and the observed symbols. In particular, they determine the state of mind of the computer after the operation is carried out.

We may now construct a machine to do the work of this computer. To each state of mind of the computer corresponds an “m-configuration” of the machine. The machine scans B squares corresponding to the B squares observed by the computer. In any move the machine can change a symbol on a scanned square or can change anyone of the scanned squares to another square distant not more than L squares from one of the other scanned {252} squares. The move which is done, and the succeeding configuration, are determined by the scanned symbol and the m-configuration. The machines just described do not differ very essentially from computing machines as defined in §2, and corresponding to any machine of this type a computing machine can be constructed to compute the same sequence, that is to say the sequence computed by the computer.

II. [Type (b)].

If the notation of the Hilbert functional calculus[7] is modified so as to be systematic, and so as to involve only a finite number of symbols, it becomes possible to construct an automatic[8] machine K which will find all the provable formulae of the calculus.[9]

Now let α be a sequence, and let us denote by Gα(x) the proposition “The x-th figure of α is 1”, so that [10] – Gα(x) means “The x-th figure of α is 0”. Suppose further that we can find a set of properties which define the sequence α and which can be expressed in terms of Gα(x) and of the propositional functions N(x) meaning “x is a non-negative integer” and F(x,y) meaning “y = x + 1”. When we join all these formulae together conjunctively we shall have a formula, U say, which defines α. The terms of U must include the necessary parts of the Peano axioms, viz.,

(Ǝu) N (u)& (x)(N(x)(Ǝy)F(x,y)) & ( F(x,y)N(y) ),

When we say “U defines α”, we mean that –U is not a provable formula, and also that, for each n, one of the following formulae (An) or (Bn) is provable.

U & F(n) Gα(u(n)),(An)[11]

U & F(n) ( –Gα(u(n))),(Bn)

where F(n)] stands for F(u, u') & F(u', u'') & … F(u(n-1), u(n)).

I say that α is then a computable sequence: a machine Kα to computeα can be obtained by a fairly simple modification of K.

We divide the motion of α into sections. The n-th section is devoted to finding the n-th figure of α. After the (n – 1)-th section is finished a double colon : : is printed after all the symbols, and the succeeding work is done wholly on the squares to the right of this double colon. The first step is to write the letter “A” followed by the formula (An) and then “B” followed by (Bn). The machine Kα then starts to do the work of K, but whenever a provable formula is found, this formula is compared with (An) and with (Bn). If it is the same formula as (An), then the figure “1” is printed, and the n-th section is finished. If it is (Bn), then “0” is printed and the section is finished. If it is different from both, then the work of K is continued from the point at which it had been abandoned. Sooner or later one of the formulae (An) or (Bn) is reached; this follows from our hypotheses about α and U, and the known nature of K. Hence the n-th section will eventually be finished; Kα is circle-free; α is computable.

It can also be shown that the numbers α definable in this way by the use of axioms include all the computable numbers. This is done by describing computing machines in terms of the function calculus.

It must be remembered that we have attached rather a special meaning to the phrase “U defines α ”. The computable numbers do not include all (in the ordinary sense) definable numbers. Let δ be a sequence whose n-th figure is 1 or 0 according as n is or is not satisfactory. It is an immediate consequence of the theorem of §8 that δ is not computable. It is (so far as we know at present) possible that any assigned number of figures of δ can be calculated, but not by a uniform process. When sufficiently many figures of δ have been calculated, an essentially new method is necessary in order to obtain more figures.

III. This may be regarded as a modification of I or as a corollary of II.

We suppose, as in I, that the computation is carried out on a tape; but we avoid introducing the “state of mind” by considering a more physical and definite counterpart of it. It is always possible for the computer to break off from his work, to go away and forget all about it, and later to come back and go on with it. If he does this he must leave a note of instructions (written in some standard form) explaining how the work is to be continued. This note is the counterpart of the “state of mind”. We will suppose that the computer works by such a desultory manner that he never does more than one step at a sitting. The note of instructions must enable him to carry out one step and write the next note. Thus the state of progress of the computation at any stage is completely determined by the note of {254} instructions and the symbols on the tape. That is, the state of the system may be described by a single expression (sequence of symbols), consisting of the symbols on the tape followed by Δ (which we suppose not to appear elsewhere) and then by the note of instructions. This expression may be called the “state formula”. We know that the state formula at any given stage is determined by the state formula before the last step was made, and we assume that the relation of these two formulae is expressible in the functional calculus. In other words we assume that there is an axiom U which expresses the rules governing the behaviour of the computer, in terms of the relation of the state formula at any stage to the state formula at the proceeding stage. If this is so, return to the indexwe can construct a machine to write down the successive state formulae, and hence to compute the required number.

https://blog.sciencenet.cn/blog-2322490-1390454.html

## 全部精选博文导读

GMT+8, 2023-9-28 08:35