计算机理论的基础是可计算性理论，而可计算性理论的基石是“图灵机”与“丘奇－图灵论题”，其意义之丰富，涵盖了从数学、算法理论、数理逻辑以及哲学意义上的深刻内容，迄今仍然未被充分解读。

一，图灵机与丘奇－图灵论题的意义

我们把图灵机理解为“算法”，并强调“算法”具有“可计算性”的意义，丘奇－图灵论题就表达了这个意义，但是包含了几个层次的意思。首先，这里的“可计算性”是指数学意义的、由递归函数定义的可计算性；第二，是指机械步骤意义上的可计算性，第三，这里的“图灵机”还指所有具体计算机的模型。

上述的第一和第二点在这里不详述，我们重点讨论“图灵机是所有具体计算机的模型”这个含义。“图灵机”这个概念本身就具有“万能”或“通用”的意义，但在特殊的情况下，如表达“判定问题”时，往往不得己使用“通用图灵机”这样的术语来表达可以把自己作为输入的图灵机，虽然这个术语有助于强调这种自我相关关系，但无形中却对“图灵机”本身所具有的“通用”性质的理解带来了更大麻烦；比如，人们常常使用“具体图灵机”来表达求解具体问题的机器，这就造成一种误导，认为“具体图灵机”也是“图灵机（模型）”，实质上，这里的“具体图灵机”是“按照图灵机（模型）设计的具体的机器”，即一台按图灵机模式构造出来的具体的机器，本质上不是图灵机（模型）。

因此，丘奇－图灵论题的一种等价性的表达就是：图灵机是所有可计算的具体的机器的“模型”，就是说，图灵机表达了所有现在以及还没有制造出来的计算机（设计蓝图）。按丘奇的解释：In the following, the words "effectively calculable" will mean "produced by any intuitively 'effective' means whatsoever" and "effectively computable" will mean "produced by a Turing-machine or equivalent mechanical device"（https://en.wikipedia.org/wiki/Church–Turing_thesis），这里的“any” 和“whatsoever” 就具有“模型”的意义。

“可计算性”这个概念具有计算能力的含义，在图灵机“模型”中，机器的计算性能力可以具体化为机器的时间或空间能力，这个时空能力大小就表现在图灵机的一个主要构造——“纸带”上。图灵机的纸带“无限长”，其意义是说，图灵机作为所有计算机的“模型”，只表达一般性的算法时空能力，不对每台计算机的运行时间和存储空间作具体性的规定；但是另一方面，作为一台具体机器，其存储器空间的大小或机器运行时间的长短就是“无限长纸带”的具体化，总是有限的，虽然如此，但是一定是可满足计算要求的，也就是说，一台机器只有在自己的存储空间和可接受的机器运行时间内以能得到确定的计算结果为条件，这台具体机器才是有意义的——effectively calculable。

然而，人们却误解了图灵机的“无限长的纸带”的意义，为此，我们摘出维基对Turing machine，Church–Turing thesis，Computable functions，Halting problem诸概念定义的部分段落，进行解读：

二，维基对Turing machine，Church–Turing thesis，Computable functions，Halting problem陈述的摘要

1，Turing machine (https://en.wikipedia.org/wiki/Turing_machine)

The machine operates on an infinite memory tape divided into cells. The machine positions its head over a cell and "reads" the symbol there. Then per the symbol and its present place in a finite table of user-specified instructions the machine (i) writes a symbol (e.g. a digit or a letter from a finite alphabet) in the cell, then (ii) either moves the tape one cell left or right, then (iii) (as determined by the observed symbol and the machine's place in the table) either proceeds to a subsequent instruction or halts the computation.

Note that every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is finite, discrete and distinguishable; it is the unlimited amount of tape and runtime that gives it an unbounded amount of storage space.

2，Church–Turing thesis (https://en.wikipedia.org/wiki/Church–Turing_thesis)

In computability theory, the Church–Turing thesis is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being ignoring resource limitations if and only if it is computable by a Turing machine.

3，Computable functions (https://en.wikipedia.org/wiki/Computable_function)

According to the Church–Turing thesis, computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. Equivalently, this thesis states that any function which has an algorithm is computable and vice versa. Note that an algorithm in this sense is understood to be a sequence of steps a person with “unlimited time and an infinite supply of pen and paper” could follow.

4，Halting problem （https://en.wikipedia.org/wiki/Halting_problem）

The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations on the amount of memory or time required for the program's execution; it can take arbitrarily long, and use arbitrarily as much storage space, before halting.

三，解读对图灵机的“无限长的纸带”的误解

我们可以看到，在上述诸概念的理解中，人们往往把作为模型的图灵机的“无限长的纸带”不知不觉地偷换成具体机器的“存储空间无限大和计算时间无限长”：unlimited amount of tape and runtime, unbounded amount of storage space; ignoring resource limitations；given unlimited amounts of time and storage space；no resource limitations on the amount of memory or time；take arbitrarily long, and use arbitrarily as much storage space。

这就是我们反复分析的概念层次的混淆：图灵机作为具体机器的“模型”，并不关心具体的运行时间和存储空间，故对纸带长度不作具体性的限制，但并不意味着具体机器可以拥有没有实际意义的时空度量，换句话说，具体机器的时空度量必须具有实际意义，于是所谓的“不计时空开销”说法就没有现实意义；另一方面，“指数时间”也不具有现实意义，因为不存在指数增长的时空。

由于人们误解了作为模型的图灵机的“无限长的纸带”的意义，于是“可计算函数”就被理解成：存在一个“算法”不计时空开销总能计算出结果的函数；“判定问题”被理解成“停机问题”，其不可判定性被理解成：不存在一个“算法”无论提供多少时空资源都无法判断任意一个程序是否停机。所以，人们也就毫不怀疑“指数时间的算法”存在，把NP认为是可判定的，从而导致NP的“不确定性”本质消失，“P versus NP”成为了世纪难题！