图灵机：在没有计算机的时候，我们如何谈论计算？( 二 ) 人类的灵魂

图灵后续进行了定义和证明，这是一篇典型的数学论文，而不是典型的工程论文，在这种文章里读者想看到讨论如何实现文中所描述的某种机制。从图灵的标题和文章中我们可以看出，图灵主要关心的是一个实数到无限位小数的计算。
这篇论文还有许多其他重要贡献：
通用图灵机，以及以数字形式为机器编码的想法
如此编码的机器的停机问题，以及对角化的不可判定性
写罢这篇论文，图灵打开了理论计算科学领域的大门。
2通用图灵机我们不能确定是什么让图灵产生了通用图灵机（UTM）的想法，但一旦他想到了，他可能会认为通用图灵机的存在是显而易见的。因为图灵机的目的就是模拟一个在办公桌上工作的职员，而图灵机的操作和文员行为一样——根据机器状态和磁带符号，根据给定的转换规则列表执行这个或那个操作——显然需要一个图灵机来执行这样的例行任务。图灵的论文对于构造的细节有些粗略，但似乎没有人介意。
而如今，我们有了已经被设计得淋漓尽致的通用图灵机。几十年前，在剑桥大学， KenMoody博士编写了一个通用明斯基注册机：

文章图片
链接：http://www.igblan.free-online.co.uk/igblan/ca/minsky.html
这样的机器有有限的寄存器，每个寄存器可以存储任意大的非负整数。它有一个有限程序，由三种不同类型的标记指令组成：
递增寄存器R并跳到标签L ，或R+→L
测试/递减寄存器R并跳转到标签L0/L1 ，或L0?R?→L1
中断。
这样的机器比图灵机更容易编程，尽管它们仍然不像真正的计算机。
Moody在N和N×N之间使用了标准的双射，将整数列表打包成单个整数。他编写了一个小型寄存器机器的小库，用于执行堆栈上推和从堆栈弹出等操作，并创建了一个让人想起真实处理器的获取-执行周期的设计。整个过程可见以下几张幻灯片。下图是机器本身：

文章图片
下图则是机器的整体结构。 (这两张图的作者都是剑桥大学理论计算科学教授AndrewPitts 。 )

文章图片
出人意料的是，这个机器的结构真简单！
3停机问题停顿问题显然是不可决定的。否则，许多数学上的猜想都会难以解决，比如费马大定理：只要写一个程序，搜索x,y,z,n>2 ，使，并问它是否终止。然而，停机的不可判定性必须被严格地表达和证明。
与大众看法相反，图灵的论文并没有讨论停机问题，而是讨论了一个与停机问题相关的特性，他称之为“循环性”（circularity）。如果图灵机「只写下有限数量的第一种符号」（即0和1），它就是循环性的。我想，循环性之所以重要，是因为图灵特别喜欢把实数近似为无限的二进制字符串。物理学家ChristopherStrachey在1965年给《计算机杂志（ComputerJournal）》的一封信中声称，图灵告诉他一个关于停机问题不可判定性的证明。

文章图片
4图灵和MauriceWilkes2009年9月， DavidP.Anderson采访了MauriceWilkes ，他对图灵的看法却与大众恰恰相反：
DavidP.Anderson：你认为图灵1936年发表的判定问题论文的重要性何在？MauriceWilkes：我觉得一个工程师会把存储程序（storedprogram）的想法当成类似三位一体的重要理论，并会说："这绝对是一流的，就应该按这办法做" 。