Turing机可以计算什么样的函数呢？根据Turing论点，任何可计算函数都是Turing可计算的。自然地，这句话的含义依赖于对术语“可计算函数”的理解。如果是按照模糊的直觉意义来理解f就像“一个函数可被算法地求值”即“由完全清晰的规则”或某些类似的东西），那么Turing论点的严格证明当然是不可能的。我们能说的只有一件事，从Euclid到Knuth的许多世纪以来从未遇到过一个算法不能转译为Turing机程序的，然而，下面我们还是要给出一个论证（虽然不太有说服力）。如果把Turing论点中的“可计算”当成“用Pascal程序可计算”，并且设想Pascal程序的语法和语义都定义好了，那么Turing论点就是一个可证明成立或不成立的明确的命题了。当然这样的证明必须建立在Pascal的语法和语义的形式化描述之上，而这从来没有人做过，然而，这类证明的简化的计算模型实际上曾经给出过，它们近似于冗长程序的正确性证明，很少人愿意去写，更少人愿意去读它。
最后，我们来介绍上面提到的支持任何可计算函数的Turing机可计算性的非形式化论证，假设你（或者任何其他人）能对给定的变量计算某个函数f.我们来描述模拟你的工作的Turing机。
你自然要用纸和铅笔（连同橡皮擦），因为能记住的信息总量是很有限的，假设你写在同样大小的纸页上：有两堆纸页，分别放在你当前页的两边；在当前页做完后，可以把它放到其中一堆上，再从另一堆顶上取下一个工作页。
……
展开
