通用图灵机

格洛丽亚·奥里吉（Gloria Origgi）

法国国家科研中心琼·尼科德（Jean Nicod）研究所哲学家。

“天地之大，万物生长，远非你的智慧所能想象。”哈姆雷特跟他的朋友霍雷肖如是说道。他以如此优雅的方式一语道破了我们生活中所有无法解决、无法处理的棘手问题。一个历来最美妙的证明最终却总会得到同样令人感到悲哀的结论：有些数学难题根本无法解决。

1936年，英国数学家阿兰·图灵构思了有史以来最为简洁和优雅的计算机，它是一种这样的设备，如他后来于1948年的论文《智能机》所描述的：

把无限长的胶带区分成许多方格的式样，将其作为无穷的存储空间，每个方格都印上符号。任何时候，机器里只会读取到其中一个符号，该符号被称为扫描符。该机器可以更改被扫描到的符号，机器的这个行为部分由那个扫描符来决定，但胶带上的其他符号不会影响机器的行为。胶带可以在机器里前进或后退，而这是机器的基本操作之一。

利用一个天才的心智，构思出一台抽象的机器，从而解决了一个曾经无法解决的决策难题。即对于每个理论的逻辑公式，是否有可能在有限的步骤内，来判定这个公式在该理论中是否有效？然而图灵指出没有这个可能性。决策问题或可判定性问题，已被数学家所熟知：1900年，在达维德·希尔伯特（David Hilbert）所列出的数学界的未解答问题列表中，决策问题排名第10位，并由此决策问题进入了20世纪大多数数学研究的日程表。其核心问题是，在有限步骤内，是否真的能够通过机械化过程来决定公式的有效性，或决定一个函数是否可以计算。于是图灵开始反问自己：“机械化过程是何含义？”而他的回答是，机械化过程就是一个可以通过机器实现的过程。这个答案非常显而易见，不是吗？

接着，图灵为每个初阶逻辑的可能公式，以及每个可能的自然数的递归函数设计出了一台机器。他是在哥德尔的不完整定理中，在初阶逻辑的公式集合和自然数的递归函数集合之间证明的逻辑等价性的基础上才完成的。而且，依据图灵的简单定义，我们确实可以在每个胶带上写下一串0和1来描述某个函数，然后给机器一张简单的指令列表（向左移动，向右移动，停止），以此让机器写下函数的证明，然后停止。

这就是他的通用图灵机。所谓通用，是因为它可以采取任何可能的字符串作为输入的符号来描述函数，并将其作为输出示范。但如果你在通用图灵机输入它对自己的描述，机器就不会停止，机器会无限地生成0和1。如此这般，所有计算机之母、数字时代的灵魂，其设计的目的都是，万物并非都能够简化为图灵机。天地之大，万物生长，远非我们的智慧所能想象。