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

“可计算数”简单被描述成实数，表达成用有限的手段计算的十进制数。虽然本文的主题表面上讲可计算数，然而几乎可以同样容易定义和研究变量为整数或实数或可计算变量的可计算函数，可计算谓词等。在每种情况下，基本的问题是一样的，我选择可计算数来解释，是因为这样可以涉及最少的技术细节。不久我希望给出可计算数与可计算函数等之间的关系，这将包括用可计算数表达的实数变量的函数理论。按照我的定义，一个数是可计算的，如果它的十进制的表达能被机器写下来。

在§9,10，我给出一些论据，想指出可计算数包括所有的能自然看作可计算的数。特别，我指出某些大的类的数是可计算的，它们包括代数数的实数部分，Bessel函数的大小的实数部分，PI, e等等。然而可计算数并不包括所有可定义的数，给出了一个可定义的但是不可计算的数。

尽管可计算数类如此之大，在许多方面类似于实数类，它仍然是可枚举。在§8章，我调查某些论证似乎证明相反的论点。通过正确应用其中一个论证，可获得与哥德尔的结论表面上相似的结论，这些结果可有应用价值，尤其是，指出（§11）Hilbertian Entscheidungsproblem没有解。

在最近的一篇论文中，Alonzo Church 引入了“effective calculability”的概念，它等同于我的“computability”，但定义却大不相同，Church也对EntscheidungsproblemJ得出类似结论。本文的附录中概述了“computability”和“effective calculability”之间的等效性证明。

第1章 计算机器

我们已经说过，可计算数是那些可用有限的手段计算而得的表达为十进制的数，这需要较明确的定义。在第九章之前，不试图对定义作论证，目前我仅说论证理由在于人类的记忆需要限制。

可将一个人计算实数与一台机器计算比较，此机器具有有限数目的条件：q1;q2;…qk，被称作“m-格局”（m-configurations）。给机器提供一条纸带（类似纸张），机器在上面运行，纸带被分为段（方格，squares），每个方格上放置一个符号。在任何时刻，只有一个方格，比如第r个方格，“在机器里”放置符号S(r)，我们可以称此方格为“扫描方格”，“扫描方格”里的符号称为“扫描符号”。“扫描符号”是机器“直接感知”的唯一符号。然而，通过改变格局，机器可以实际记忆已经“见过（扫描）”的符号。机器在任何时刻可能的行为由m-格局qn，扫描符号S(r)决定，这对（qn，S(r)）称为“格局”：于是，格局决定机器可能的行为。在有些格局，扫描方格是空的（即没有符号），机器就在扫描方格上写下一个新的符号；在别的格局，它擦掉扫描符号。机器也可能改变正在扫描的方格，但是仅仅向左右移动一个方格。此外，对任何一个这样的操作，m-格局可能变化。某些写下的符号将形成数字序列（ sequence of figures），它是正在计算的表达为十进制的实数，别的符号只是“辅助记忆”的粗糙纪录，只有那些粗糙纪录可能被擦掉。

我的观点是，这些操作包括了所有用在计算一个数时所需的操作，为此论点辩护要在读者较熟悉机器理论后才变得较容易。在下一节，我将着手发展此理论，假设读者已经知道“机器”，“纸带”，“扫描”等。

第2章 定义

自动机（Automatic machines）

如果每个阶段机器的运动（在§1的意义上）完全由格局确定，我们称此机器为«自动机»（a-machine）。

为了某种目的，我们可能使用一些机器（choice machines or c-machines），它的运动部分由格局决定（因此在§1中使用“可能”一词）。当这样的机器到达一个这样模棱两可的格局时，只有当外界的操作做某个任意的选择，它才能继续运行。如果我们用机器处理公理系统时会出现这样的情况，在本文中，我只处理自动机，因此往往忽略前缀a-。

计算机器（Computing machines）

如果一台机器打印两类符号，第一类（称为数字）全是0和1，其它被称为第二类符号，则机器将被称为“计算机器”。如果给机器装置一条空白纸带，让它运动起来，从正确的初始m－格局出发，机器打印的第一类符号的子序列称作机器计算的序列；在表达为二进制的十进制实数前放上小数点，称作“机器计算的数”。

在机器运动的任何阶段，扫描方格的数，在纸带上所有符号的完整序列，及m－格局，被说成是描述那时刻的“完全格局”。机器和纸带在一系列完整格局之间的变化被称作“机器的运动”。

循环和非循环机器（Circular and circle-free machines）

如果计算机器不再写下第一类有限数目的符号，被称作“循环（Circular）”；否则，被称作“无循环（circle-free）”。

机器是“circular”，指如果一台机器达到一个格局，从此不再运动，或者即使继续运动，只能打印第二类符号，而不能打印任何第一类符号。“circular”的意义将在第8章解释。

可计算序列和可计算数（Computable sequences and numbers）

一个序列被说成“可计算的”，如果能够通过一台“circle-free machine”计算而得。一个数是“可计算的”，如果它与由“circle-free machine”计算的数只差一个整数。

我们应该避免混淆，说可计算序列比说可计算数更经常。

二，图灵文章《论可计算数及其在判定问题上的应用》的第1，章原文

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 X, 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.

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 [1] . These results {231}  have valuable applications. In particular, it is shown (§11) that the Hilbertian Entscheidungsproblem can have no solution.

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 EntscheidungsproblemJ. The proof of equivalence between "computability" and "effective calculability" is outlined in an appendix to the present paper.

1. Computing machines.

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.

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 q1, q2, ..., qR 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 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 qn and the scanned symbol S(r). This pair qn, 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 1eft. In addition to any of these operations the m-configuration may be changed. Some of the symbols written down {232} 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.

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.

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-.

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.{233}

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.  

参考文献：

【1】图灵论文“On Computable Numbers, with an Application to the Entscheidungsproblem”原文：https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf