本节书摘来自华章计算机《计算复杂性：现代方法》一书中的第1章，第1.7节，作者 ［美］桑杰夫·阿罗拉（Sanjeev Arora），博阿兹·巴拉克（Boaz Barak），译 骆吉洲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.7　定理1.9的证明：O(TlogT)时间的通用模拟

本章学习内容

●存在许多等价方法对计算过程进行数学建模。我们采用标准的图灵机定义。

●图灵机可以表示为位串。存在通用图灵机，它可以（代价很小地）模拟任意给定的用位串表示的图灵机。●存在函数不能被任意图灵机计算，不管计算时间多长。停机问题是不可计算的。●类P是由可以被图灵机在多项式时间内求解的所有判定问题构成的。我们称P中的问题是可以被高效求解的。●图灵机定义中(带的数量、字母表大小等)底层结构的选取不是本质的，因为它们不会改变P的定义。

本章注记和历史

尽管算法的研究已持续千百年，并且一些计算装置也早在二十世纪以前就被发明出来（最值得关注的是十九世纪中叶由查尔斯·巴贝奇(Charles Babbage)发明的差分机和分析机）。但确切地讲，现代计算机科学的基础直到二十世纪三十年代才真正奠定。

1931年，库尔特·哥德尔证明了在自然数上肯定成立的命题是固有的不可证明的，这一结果震惊了整个数学界，同时粉碎了希尔伯特在1900年提出的旨在建立完备算术公理的雄心勃勃的研究计划。1936年，阿隆佐·邱奇（Alonzo Church）定义了一种称为λ演算的计算模型（多年后由此产生了LISP这种程序设计语言），并证明了该计算模型上存在固有的不可计算函数［Chu36］。几个月之后，阿兰·图灵独立地引入了他的图灵机，并证明了图灵机上也存在固有的不可计算函数［Tur36］。图灵还介绍了能加载任意程序的通用图灵机的思想。前述的两种计算模型已被证明是等价的。然而，正如邱奇自己所述，图灵机的优点在于“根据普通意义（而非显式的定义）就能立即明确地认定高效性”。文集［Dav65］收录了可计算理论方面的许多影响深远的开创性论文。西普赛尔(Sipser)的书［Sip96］的第二部分很好地对可计算理论作了一般性介绍，而［Rog87,HMU01,Koz97］等书则相对深入地对此进行了讨论。这些书也涵盖了自动机理论，它是计算理论的另一个领域，本书目前未做相关讨论。本书网站提供了可计算理论和自动机理论相关信息的链接。

二战期间，图灵设计了机械密码破译装置，它在破译德军的“谜”密码的过程中发挥了关键作用，同时该项成就也改变了战争的进程（参见传记［Hod83,Lea05］）。二战后，建造通用电子计算机的任务在英国和美国同时进行，建造过程的一个关键人物是约翰·冯·诺依曼。这位极其多产的科学家除参加了曼哈顿项目的整个过程之外，还发现了经济博弈论。截止到目前，所有的数字计算机本质上均采用了“冯·诺依曼体系结构”，这是由他在设计最早的数字计算机EDVAC的过程中提出的［vN45］。