Turing之后的不可计算性.pdfVIP

Turing之后的不可计算性 S．BarryCooper 2012年是AlanTuring(图灵)的百年诞辰．下面这两篇文章的灵感均来 自于Alan Turing的研究工作．关于Turing生活和工作的百年诞辰庆典的更多信息，详见 http：llwww．mathcomp．1eeds．ac．uk／turing2012／． 1．生活在可计算的世界 那些上了年纪的人也许还记得，大家曾痴迷于 GeorgeGamow的有关数学与科学的 畅销书，其中最著名的一本书叫 从一到无穷大 (OneTwoThree…Infinity)》．Gamow 让仅有二维平面体验的我们设想生活在一个二维气球的表面．然后，他告诉我们如何通 过纯粹的二维观察来发现它的三维曲面特征．图1是他在 1961年版的该书的p．103给出 的示意图． 算法作为一种穿越我们四维空间的方法，已伴随人类几千年了．算法为我们掌控和 理解 日常生活的方方面面提供了秘诀．目前，算法是作为计算机程序出现的．算法或计算 机程序，可以认为是一种有关它们本身的归因维度．此时就不得不提出一个新的问题： 是否存在非算法的归因维度?若存在，这意味着什么? Gamow的例子表 明，生活在二维空间去寻找第三维 存在的证据是棘手的．然而事实 的确 如此，因为我们能 够找到证据．当然，如果我们借助图1所表述的数学模 型，缺失的那个维度在我们面前就变得清晰了，这是因为 我们可以总览全局．尽管从数学角度的总览有助于我们更 好地理解 曲面空间的属性，但它并没有指明该模型与我们 的世界有何关系．我们 仍 需在二维世界里来看三角形， 然后将现实世界和数学很好地结合起来从而发挥模型的 全部功效． 早在 20世纪 30年代，KurtG6del(哥德尔)、Stephen Kleene(克林)、AlonzoChurch(丘奇)和AlanTuring等 图 1 二维平面体验的科学家在 人就建立了可计算归因维度的数学模型．这使得Church 平面和曲面中检验有关三角形内 和~ring能够运用他们的模型在该维度之外来探索不可 角和的欧氏定理 [14] 计算性的新维度． 译 自tNoticesoftheAMS，Vo1．59(2012)，No．6，P．776-784，IncomputablilityafterAlanTuring，S． BarryCooper，figurenumber6．(原文中有7幅图，译文只刊出6幅，因为原文中图6的版权未获得许 可．)Copyright⑥2012theAmericanMathematicalSociety．Reprintedwithpermission．Allrights reserved．美国数学会与作者授予译文出版许可． S．BarryCooper是利兹 (Leeds)大学的数学教授，同时也是 “Thring百年咨询委员会 (TCAC)”的主 席．他的邮箱地址是：pm~6sbc~maths．1eeds．ac．uk． 本文的准备工作是作者在访问 IsaacNewton (牛顿)数学科学研究所期间参与 “语法和语义：Alan Turing的遗产，’项目时完成的． ． 296 ． 24岁的Turing做出的特别重要的成果是对新的 类机器 (machine—like)模型的可计 算范围的研究．Xhring因Turing机而闻名，这是任何人事先都没有想到的．他的想法是 利用 G6del编码技巧将 Turing机程序转换为机器能够计算的数据，并因此产生了通用 (universa1)~fhring机．通用 Turing机能将其他 任何 给定机器的代码作为输入数据，并 能像给定机器一样准确地计算．我们不必亲 自建造