图灵在1936年的论文（《论可计算数及其在判定问题上的应用》）的前言、第一、二章中提出了几个基本概念（见博文：可计算性——图灵1936年论文解读（1）），这些概念与当时数学和数理逻辑中一些观念不同，也与以前关于“算法”的直觉概念有别，图灵突出了机器计算的直观性，这些都是以后称之为“图灵机”的基础，这里我们先分析“可计算数（computable number）”。

一，可计算数

在可计算性理论中，人们一般讨论“可计算函数”，然而图灵的论文谈及的是“可计算数”。图灵之所以谈“可计算数”，是因为“虽然本文的主题表面上讲可计算数，然而几乎可以同样容易定义和研究变量为整数或实数或可计算变量的可计算函数，可计算谓词等。在每种情况下，基本的问题是一样的，我选择可计算数来解释，是因为这样可以涉及最少的技术细节”［1］。

图灵说：“可计算的”数，简单地说就是其十进制形式可用有限手段计算出来的实数（The “computable” numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.）。这个定义实质上就把“可计算的”用“有限手段的计算”定义了，后者就指机器结构和过程，也就是论文以下的“图灵机”的思想实现。

图灵进一步强调：按照我的定义，一个数是可计算的，如果它的十进制的表达能被机器写下来（According to my definition, a number is computable if its decimal can be written down by a machine.）。这样就明确地把数学意义上的“可计算的”数表达为“可计算的”机械过程，揭示了算法的“能行性”本质（见博文：NP理论的基本概念（2）：“判定问题”与“停机问题”）。

图灵强调可计算数一定要由机器写下来，这是因为机器能得到的最后结果一定是确定的，以此倒推机器的算法步骤关系，这是图灵的思想实验最关键的一步，由此揭示了“机械步骤”的实时（the Actual Time）性本质。这正是“算法”这个直觉概念所隐含的一个本质，也是“图灵机”的本质特征。

二，例子

图灵在论文的第三章给出一个可计算数（序列）：010101...，计算此序列的机器就是在第一、第二章定义Computing Machine：

此机器有四个状态（m-configuration）：“ b”,  “c”, “z”, “e” ，能打印“0”和“1”。机器的行为被描述在下面的表中，其中“R” 表示机器移动去扫描当前方格的右边方格。“P” 表示“打印”。这个表被理解成，机器在头二列表达的格局下，执行第三列的操作，进入最后一列的状态。当第二列是空白时，可理解为第三第四列的行为应用于任何符号和无符号。

格局             行为

b     None     P0,R    c

c     None     R         e

e     None     P1,R    z

z     None     R         b

机器开始于状态b和一条空白纸带，打印完01又回到状态b，再重复打印01，形成无限长的字符串010101...，这就是一个最简单的机器计算步骤过程。

参考文献

［1］《论可计算数及其在判定问题上的应用》的第三章部分原文（https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf）：

3. Examples of computing machines.

I. A machine can be constructed to compute the sequence 010101.... The machine is to have the four m-configurations “ b”, “c”, “z”, “e” and is capable of printing “0”, and “1”. The behaviour of the machine is described in the following table in which “R” means “the machine moves so that it scans the square immediately on the right of the one it was scanning previously”. Similarly for “L”. “E” means the scanned symbol is “erased” and “P” stands for “prints”. This table (and all succeeding tables of the same kind) is to be understood to mean that for a configuration described in the first two columns the operations in the third column are carried out successively, and the machine then goes over into the m-configuration described in the last column. When the second column is left blank, it is understood that the behaviour of the third and fourth columns applies for any symbol and for no symbol. The machine starts in the m-configuration b

with a blank tape.

Configuration Behaviour

b     None     P0,R     c

c     None     R          e

e     None     P1,R     z

z     None     R          b