第2章 图灵的计算王国

张江

图灵机（Turing Machine）与计算理论（Theory of Computation）是人工智能乃至整个计算机科学的理论基础。邱奇-图灵论题（Church-Turing Thesis）告诉我们，一切可计算过程都可以用图灵机模拟。因此，无论如何人工智能都无法逃脱图灵机可计算理论的范畴。本章从图灵可计算理论的基础出发，忽略掉一切实用的工程细节，来讨论计算机可以做和不可以做的事情。从这些讨论中，我们可以站在一定的理论高度来窥探人工智能的前进方向。

本章首先会引入图灵机模型，为了让读者对这个概念有比较直观的理解，我采用了一个人工生命“小虫”的比喻来叙述。接下来会介绍跟图灵机有关的概念，例如什么是模拟，什么是“万能计算”（即通用计算，universal computation）等。最后是关于图灵停机问题的探讨，我个人认为很有可能未来对人工智能的重大突破都来源于对图灵停机问题的深入理解。另外，我除了用自己的方式介绍一些现有的基本概念之外（为了尽量表达得清楚明白，我不得不放弃理论论证的严格性），还探讨了很多我认为很有价值而计算理论却没有涉及的问题。在这部分内容上我都标上了*号，我尝试着给出了自己的思考结果，而没有经过严格的理论推敲，希望读者能有选择地看待这些问题和观点。