图灵的秘密

[美] 佩措尔德
图灵机(Türing Machine):1936 年,阿兰·图灵写了一篇关于计算机器的设计和局限性的论文,由此,它们被冠以了图灵的名字。这个变音ü 其实是不必要的,这只是大家推测,这么难以理解的东西一定是德国人写的。——摘自Faster Than Thought: A Symposium on Digital Computing Machines(1953) 引 言研究过计算机的历史、技术或理论的人,都会接触到“图灵机”这个概念。在1936年,为帮助解决数理逻辑中的一个问题,英国数学家阿兰·图灵(1912—1954)提出了图灵机。它是一种纯属虚构的计算机,连计算机假设也算不上。而由此得到的意外收获是,图灵创立了一个新的研究领域——计算理论(或可计算性),它主要研究数字计算机的功能和局限性。尽管图灵机是一种并不太合理的计算机,但由于其自身极其简单而大放异彩。最基本的图灵机只能进行一些简单的操作。如果连这些操作都不能做,那么这台机器干脆什么都别做了。然而,只要将这些简单的操作组合起来,图灵机就能够进行现代数字计算机可以执行的任何计算。拨开云雾见天日,通过考查计算机的原始基础,我们就能够更好地理解数字计算机的能力和局限性,这二者同样重要。尽管有人早就论证过计算机可以做什么,但在这种论证出现多年之前,图灵就证明了计算机永远都做不到的事。图灵机仍然是被阐述和探讨的热门话题,你可以试试用喜爱的网络搜索引擎搜索“图灵机”。然而,我猜很少有人会阅读阿兰·图灵描述他这项创造的原始论文。或许,这与论文的标题“On Computable Numbers, with an Application to the Entscheidungsproblem”(“论可计算数及其在判定性问题上的应用”)有关。即使你会读最后那个单词(试试看,将重音放在第二个音节上,把这个音节发成类似“shy”的音,这就差不…