维特根斯坦曾与波普尔对谈半个小时,就有人八卦了一本书;而维特根斯坦和图灵智力交锋了一学期,却很少有人评论,。。。 这是因为人们对 “ 思想 ” (在与 “ 内容 ” 本身的相对的意义上)比对(人的) “ 思想形式 ” (与 “ 内容 ” 的实体相对应)上更不容易看到事物的深层本质。 1939 年,维特根斯坦( Wittgenstein , 1889 - 1951 )在剑桥大学开讲 ” 数学基础 ” ( Foundations of mathematics ),时年五十岁;图灵( Alan Turing , 1912 - 1954 )二十七岁,刚在美国普林斯顿的数学家、逻辑学家丘奇( Alonzo Church , 1903 - 1995 )的指导下完成博士论文 “ 基于序数的逻辑系统 ” ( Systems of Logic Based on Ordinals ),回到英国。图灵在剑桥大学申请讲师未遂,接着当研究员,同年在学校开一门数理逻辑的课程,取名 “ 数学基础 ” ,看了学校的课程表后才知道维特根斯坦也开一门同名课程,于是决定去旁听,有了维特根斯坦和图灵一学期的精彩对话!记载在维特根斯坦的几个学生整理的书中《维特根斯坦剑桥数学基础讲义, 1939 》。 这里把关于 “ 图灵与维特根斯坦关于矛盾和悖论的对话 ” 翻译出来。 一,译文 维特根斯坦: “ 说谎者悖论 ” 使人感到困惑,这从某种意义上说很奇怪,。。。。是这样的:如果一个人说 “ 我在说谎 ” ,就得出:我没说谎,所以我说谎;我说谎,所以我没说谎。好吧,那又如何呢?你可以这样继续下去, 直到说得小脸发青。为什么不? 没关系,。。。 现在假设一个人说 “ 我在撒谎 ” ,而我说 “ 因此你没撒谎,因此你撒谎,因此你没撒谎 ...” – 哪有问题? 没有,除了没有用,这只是一个没意义的语言游戏而已,为什么会有人因此而兴奋? 图灵:让大家困惑的是,在一般情况下,有矛盾肯定就有错,但在这个例子中,大家不知道哪出错了。 维特根斯坦:是的,但没什么错啊。 有一种特殊的数学方法,即反证法,也称 “ 避免矛盾 ” 。 在这种方法中,人们暴露出矛盾,然后再指出避免矛盾的出路,但这并不意味着矛盾就是恶魔。 有人可能会说: “ 矛盾是问题的来源。 ” 答案是:那么,就不要从矛盾中得出任何结论; 将此作为规则。 您可能会说:当我们得出矛盾时,总是有时间去解决它。当我们得出矛盾时,我们不应该简单地说: “ 这没有用 - 我们不会从中得出任何结论 ” ? 图灵:除非有实际情况,否则不会有真正的危险。在实际情况下,桥梁会倒塌或发生类似情况。 桥(第 22 讲) 维特根斯坦:上次有人提出逻辑或数学中的矛盾在实际情况中的危险,图灵指出桥梁可能倒塌。 说一座桥可能因矛盾而倒塌,听起来有些不对劲。我们对导致桥梁倒塌的想法有错误。 ( a )我们掌握的错误的物理法则 – 错误的系数。 ( b )计算有误 – 有人乘法做错了。 第一种情况显然与矛盾无关;第二个不太清楚。 图灵:除非你知道其中没有隐藏着矛盾,否则你不会对你的计算充满信心。 维特根斯坦:在我看来那里有严重错误,因为你的演算给出了某些结果,并且你希望桥梁不倒塌。我要说的是,出问题的可能只有两种方式:或者桥梁倒塌,或你在计算中犯了错误 - 例如,你乘法做错了,但是你似乎认为可能有第三种错误:演算是错误的。 图灵:不。我反驳的是桥梁倒塌。 维特根斯坦:但是你怎么知道它倒塌? 这不是物理问题吗? 图灵:如果有人接受了弗雷格的符号系统,给予某人乘法的技巧,那么通过使用罗素悖论,他可能会得到错误的乘法。 维特根斯坦:这是做一些我们不称做乘法的事情 …… 我要讲的是弗雷格和罗素的逻辑无论如何都不是算术的基础 - 不管矛盾还是不矛盾。 (来自第 22 讲和第 23 讲) 二,原文 The Turing/Wittgenstein exchange on contradiction and paradox (Lecture XXI) Wittgenstein: ‘Think of the case of the Liar. It is very queer in a way that this should have puzzled anyone ... Because the thing works like this: if a man says “I am lying” was say that it follows that he is not lying, from which it follows that he is lying and so on. Well, so what? You can go on like that until you are black in the face. Why not? It doesn’t matter… Now suppose a man says “I am lying” and I say “Therefore you are not, therefore you are, therefore you are not...” – What is wrong? Nothing. Except that it is no use; it is just a useless language-game, and why should anybody be excited?’ Turing: What puzzles one is that one usually uses a contradiction as a criterion for having done something wrong. But in this case one cannot find anything done wrong. Wittgenstein: Yes – and more: nothing has been done wrong. Wittgenstein: There is a particular mathematical method, the method of reduction ad absurdum, which we might call “avoiding the contradiction”. In this method one shows a contradiction and then shows the way from it. But this doesn’t mean that a contradiction is a sort of devil. One may say, “From a contradiction everything would follow.” The reply to that is: Well then, don’t draw any conclusions from a contradiction; make that the rule. You might put it: There is always time to deal with a contradiction when we get to it. When we get to it, shouldn’t we simply say, “This is no use – and we won’t draw any conclusions from it”? Turing: The real harm will not come in unless there is an application, in which case a bridge may fall down or something of that sort. The Bridge (Lecture XXII) Wittgenstein: It was suggested last time that the danger with a contradiction in logic or mathematics is in the application. Turing suggested that a bridge might collapse. Now it does not sound quite right to say that a bridge might fall down because of a contradiction. We have an idea of the sort of mistake which would lead to a bridge falling. (a) We’ve got hold of a wrong natural law – a wrong coefficient. (b) There has been a mistake in calculation – someone has multiplied wrongly. The first case obviously has nothing to do with having a contradiction; and the second is not quite clear. Turing: You cannot be confident about applying your calculus until you know that there is no hidden contradiction in it. Wittgenstein: There seems to me to be an enormous mistake there. For your calculus gives certain results, and you want the bridge not to break down. I’d say things can go wrong is only two ways: either the bridge breaks down or you have made a mistake in your calculation – for example, you multiplied wrongly. But you seem to think that there may be a third thing wrong: the calculus is wrong. Turing: No. What I object to is the bridge falling down. Wittgenstein: But how do you know that it will fall down? Isn’t that a question of physics? Turing: If one takes Frege’s symbolism and gives someone the technique of multiplying in it, then by using a Russell paradox he could get a wrong multiplication. Wittgenstein: This would come to doing something which we would not call multiplying... The point I’m driving at is that Frege and Russell’s logic is not the basis for arithmetic anyway – contradiction or no contradiction. (from Lectures XXII and XXIII) 参考文献: 【 1 】 Turing and Wittgenstein on Logic and Mathematics - The Eighteenth British Wittgenstein Society Lecture, Ray Monk, https://www.britishwittgensteinsociety.org/wp-content/uploads/documents/lectures/Turing-and-Wittgenstein-on-Logic-and-Mathematics.pdf 【 2 】图灵对掐维特根斯坦:这次维特没有用拨火棍却显出了尊敬, https://www.thepaper.cn/newsDetail_forward_1361179
图灵的“论可计算数及其在判定问题上的应用”(On Computable Numbers, With an Application to the Entscheidungsproblem)是1936年的工作,而他的博士论文“基于序数的逻辑系统”(Systems of Logic Based on Ordinals)是1938年完成的。前者可以说是计算机理论中的“圣经”,但后者却给理论和认知带来了很大的困惑,我们认为这种结果主要是由于对图灵论文的误解造成的。 图灵在这篇论文中提出了“神谕”这样一种假设,完全不是为了“证明”“超计算”这个概念,恰恰相反,图灵说:“假设我们拥有一种可以解决不可判定问题的一般方法,那么可以称这种方法为神谕。对于这个神谕,我们除了知道它肯定不是一台机器外,无法知道更多的了”(Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine.)。 可能是为了突破“图灵机”的限制的缘故,大量的“超计算”等研究从各方面一直开展着,但是迄今为止,并没有真正的突破(相关的物理学和纯数学上研究的不在此例)。 “NP完全性”(NP-Completeness)是柯克(Cook)1971年开创性的工作(The Complexity of Theorem-Proving Procedures),在他以前虽有涉及此类性质的一些研究,但并不成为专门领域理论,更没有造成像“千禧年难题”(P versus NP)这样的影响;而且随着计算机、互联网、人工智能研究的高速发展,计算机的能力限度越来越成为迫切的问题,但目前为止所有概念和理论均没有给出现成的答案。 我们对NP理论研究工作基于经典的可计算机理论(包括图灵机),从目前存在的困难出发,追本溯源,寻求可计算性与不确定性的本质及其关系,由于学力有限,不可能涉及这个领域内方方面面,因此对所讨论的问题有论域的限制,但并不排斥网友们的广泛讨论。
从 Enigma 到“鳄鱼追斑马” 按:本文分为两个部分.这两个部分有没有关系或者有什么样的关系,我不知道...... I. Enigma 我终于抢在彻底下线前去电影院看完了《模仿游戏》( The Imitation Game, 放心没有“剧透” )。 大概几周以前,我偶然在影院门口看到了这部电影的海报。由于海报上信息较少(或者我没有察觉到),我完全没有想到 Benedict Cumberbatch 与 Alan Mathison Turing 有任何联系(说实话,一点也不像!)。我唯一注意到的信息是海报左下方一个极限公式的书写“瑕疵”。多亏这个“瑕疵”,我估计这可能是部有关数学家的电影,便回去上网搜了搜,这才知道传主正是 Turing。 上周我抽空到“西财”附近的一家影院准备看这部片子,却被告知上映两天就在该影院下线了。无奈就这样捱到了今天。 最早知道 Turing, 源自 小时候读一本大概叫《中外科学家故事》的书,其中一篇大约名为《一枚数学的珍贝》(那本书各个篇目的名字都很有特点,至今都还记得,比如牛顿那篇叫“沃尔索普村燃起的科学之火”,可惜书的确切名字和出版社实在记不清了)就是讲 Turing 破译 Enigma 的故事。前些年又在《科幻世界》上读到一篇长铗写的科幻短篇《 ACE 小姐的心事》,主体情节的“底本”也不外乎这段故事。 我对计算机这门学科的历史并不了解。仅就我掌握的资料,这部改编自B iography of Alan Turing( Alan Turing: The Enigma ) 的电影对涉及的计算机科学概念做了较大程度的“简化”,对相关史实尤其人物关系也做了不少“调整”,甚至包括 Turing 的性格和人际关系(为什么一定要塑造成 monster 呢?)。但是我们毕竟没必要在《三国演义》里找“曹操”。我注意到,当电影进行到后半段时,放映厅变得很安静——我想一部电影达到这样的效果,已经足够了。 在某种程度上,一个多月前美国联邦最高法院的那一项裁定使得这部电影变得十分应景,其中关于人性或者人与人关系的反思,在传播价值上已经远远盖过了其中的数学或计算机科学元素。但对我来说, Turing 仍然是最初留下的印象——那个破译了不可能破译的 Enigma 的 数学家。 II. 鳄鱼追斑马 让我下定决心去看看 Turing 的原因是今天早上看到一则新闻《苏格兰“高考”数学难哭考生,分数线被降至34分》( http://life.gmw.cn/2015-08/07/content_16574089.htm ) 以前就看过 A-Level 的高中物理题,我辈只能 smilence。 这次看了看据说是拉低了10.7万考生的及格分数线(从去年45到今年33.8,60分可拿A——“60分万岁”乎?)的数学题——1.4万考生心目中的“不可能完成的迷题”—— Enigma??? 联系到近来“九九乘法表”(我以前真的天真地以为全世界小朋友都会)、“广播体操”之类的定向出口,“英国人数学不好”的说法甚嚣尘上..... The Great Britain, The Great Britain! Where came Maxwell and Newton, Where went Dirac and Hamilton ...... Few heroes or lots of strangers, That is an Enigma! Alan Mathison Turing 1912~1954
Chinese Turing Tests?? Challenging my Chinese dependency parser with puns. The real thing is, structural ambiguity is detectable, but not easily decodable. As for puns, forget it! Do you remember the last time you yourself, as an intelligent being designed by almighty God, were puzzled by jokes of puns? RE: 立委,测试你分析工具的图灵试题来了 大学里有两种人不谈恋爱:一种是谁都看不上,另一种是谁都 看不上。 parse 后一看,居然 合一 (unify)了:真地歇菜了?? 作者: 立委 日期: 10/11/2012 17:55:00 但是,(镜子曰,世界上怕就怕但是二字),请注意同样的string “是谁都看不上” 是怎样分析的:分析出两种意义 【意义1】是这么断句的:【是谁】 【都看不上】:【谁】 是【是】的逻辑宾语(Undergoer) 【意义2】则是:【是】 【谁都看不上】:【谁】 是【看不上】的逻辑主语(Actor) 哈哈,不傻吧,my baby 当然,同样的string,在目前是无法指望机器输出不同结果的。 实用的 parsing 技术从来没有超出语句级别的 context 来解码句法结构。 据说,类似的中文“图灵试题”还有: 大学里有两种人最容易被甩:一种人不知道什么【叫做】爱,一种人不知道什么叫【做爱】。 这些人都是原先喜欢一个人,后来喜欢一个人。 老友说,最后一句的精彩之处不在分词,在重音位置。机器只能歇菜 当然这些都是戏谑性的 puns,连人都会被绕晕,根本不用做 real life 系统的人分心。实际语言现象中,有的是 low hanging food, 很多 tractable 的问题好多系统都未及涉及呢,教机器识别 puns 这样劳而无功的勾当,根本排不上号。 【维基: 图灵测试 】 http://en.wikipedia.org/wiki/Turing_test 《立委科普:机器可以揭开双关语神秘的面纱》 【置顶:立委科学网博客NLP博文一览(定期更新版)】
图1 邹晓辉归纳的“六代编程语言”基本特征 图2邹晓辉进一步简化的“形式化双重路径” 最近在总结自己发现并强调的“(自然语言)形式化双重途径”的探索、研究和思考的过程中,不由自主地 想到 回顾图灵奖(Turing Award)获得者们在理论计算机、人工智能、编程语言几个方面的贡献,结果发现自己的猜测或估计真的没错,大部分图灵奖(Turing Award)获得者们的贡献真就是与 编程语言 及其开发平台、操作系统和数据库等软件及其 理论思考 联系在一起的。 附录: 回顾图灵奖(Turing Award)获得者们的贡献,可以发现:...... Year Recipients Citation 1966 Alan J. Perlis For his influence in the area of advanced programming techniques and compiler construction 1967 Maurice V. Wilkes Professor Wilkes is best known as the builder and designer of the EDSAC , the first computer with an internally stored program . Built in 1949, the EDSAC used a mercury delay line memory . He is also known as the author, with Wheeler and Gill, of a volume on " Preparation of Programs for Electronic Digital Computers " in 1951, in which program libraries were effectively introduced 1968 Richard Hamming For his work on numerical methods , automatic coding systems , and error-detecting and error-correcting codes 1969 Marvin Minsky artificial intelligence 1970 James H. Wilkinson For his research in numerical analysis to facilitate the use of the high-speed digital computer , having received special recognition for his work in computations in linear algebra and "backward" error analysis 1971 John McCarthy McCarthy's lecture "The Present State of Research on Artificial Intelligence " is a topic that covers the area in which he has achieved considerable recognition for his work 1972 Edsger W. Dijkstra Edsger Dijkstra was a principal contributor in the late 1950s to the development of the ALGOL , a high level programming language which has become a model of clarity and mathematical rigor. He is one of the principal proponents of the science and art of programming languages in general, and has greatly contributed to our understanding of their structure, representation, and implementation. His fifteen years of publications extend from theoretical articles on graph theory to basic manuals, expository texts, and philosophical contemplations in the field of programming languages 1973 Charles W. Bachman For his outstanding contributions to database technology 1974 Donald E. Knuth For his major contributions to the analysis of algorithms and the design of programming languages , and in particular for his contributions to " The Art of Computer Programming " through his well-known books in a continuous series by this title 1975 Allen Newell and Herbert A. Simon In joint scientific efforts extending over twenty years, initially in collaboration with J. C. Shaw at the RAND Corporation , and subsequentially with numerous faculty and student colleagues at Carnegie Mellon University , they have made basic contributions to artificial intelligence, the psychology of human cognition, and list processing 1976 Michael O. Rabin and Dana S. Scott For their joint paper "Finite Automata and Their Decision Problem," which introduced the idea of nondeterministic machines , which has proved to be an enormously valuable concept. Their (Scott Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field 1977 John Backus For profound, influential, and lasting contributions to the design of practical high-level programming systems , notably through his work on FORTRAN , and for seminal publication of formal procedures for the specification of programming languages 1978 Robert W. Floyd For having a clear influence on methodologies for the creation of efficient and reliable software , and for helping to found the following important subfields of computer science : the theory of parsing , the semantics of programming languages , automatic program verification , automatic program synthesis , and analysis of algorithms 1979 Kenneth E. Iverson For his pioneering effort in programming languages and mathematical notation resulting in what the computing field now knows as APL , for his contributions to the implementation of interactive systems , to educational uses of APL, and to programming language theory and practice 1980 C. Antony R. Hoare For his fundamental contributions to the definition and design of programming languages 1981 Edgar F. Codd For his fundamental and continuing contributions to the theory and practice of database management systems , esp. relational databases 1982 Stephen A. Cook For his advancement of our understanding of the complexity of computation in a significant and profound way 1983 Ken Thompson and Dennis M. Ritchie For their development of generic operating systems theory and specifically for the implementation of the UNIX operating system 1984 Niklaus Wirth For developing a sequence of innovative computer languages , EULER , ALGOL-W , MODULA and PASCAL 1985 Richard M. Karp For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness 1986 John Hopcroft and Robert Tarjan For fundamental achievements in the design and analysis of algorithms and data structures 1987 John Cocke For significant contributions in the design and theory of compilers, the architecture of large systems and the development of reduced instruction set computers (RISC) 1988 Ivan Sutherland For his pioneering and visionary contributions to computer graphics , starting with Sketchpad , and continuing after 1989 William (Velvel) Kahan For his fundamental contributions to numerical analysis . One of the foremost experts on floating-point computations. Kahan has dedicated himself to "making the world safe for numerical computations." 1990 Fernando J. Corbató For his pioneering work organizing the concepts and leading the development of the general-purpose, large-scale, time-sharing and resource-sharing computer systems, CTSS and Multics . 1991 Robin Milner For three distinct and complete achievements: 1) LCF , the mechanization of Scott's Logic of Computable Functions, probably the first theoretically based yet practical tool for machine assisted proof construction ; 2) ML , the first language to include polymorphic type inference together with a type-safe exception-handling mechanism; 3) CCS , a general theory of concurrency . In addition, he formulated and strongly advanced full abstraction , the study of the relationship between operational and denotational semantics . 1992 Butler W. Lampson For contributions to the development of distributed, personal computing environments and the technology for their implementation: workstations , networks , operating systems , programming systems , displays , security and document publishing . 1993 Juris Hartmanis and Richard E. Stearns In recognition of their seminal paper which established the foundations for the field of computational complexity theory . 1994 Edward Feigenbaum and Raj Reddy For pioneering the design and construction of large scale artificial intelligence systems , demonstrating the practical importance and potential commercial impact of artificial intelligence technology. 1995 Manuel Blum In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking . 1996 Amir Pnueli For seminal work introducing temporal logic into computing science and for outstanding contributions to program and systems verification . 1997 Douglas Engelbart For an inspiring vision of the future of interactive computing and the invention of key technologies to help realize this vision . 1998 Jim Gray For seminal contributions to database and transaction processing research and technical leadership in system implementation. 1999 Frederick P. Brooks, Jr. For landmark contributions to computer architecture , operating systems , and software engineering . 2000 Andrew Chi-Chih Yao In recognition of his fundamental contributions to the theory of computation , including the complexity-based theory of pseudorandom number generation , cryptography , and communication complexity . 2001 Ole-Johan Dahl and Kristen Nygaard For ideas fundamental to the emergence of object-oriented programming , through their design of the programming languages Simula I and Simula 67 . 2002 Ronald L. Rivest , Adi Shamir and Leonard M. Adleman For their ingenious contribution for making public-key cryptography useful in practice. 2003 Alan Kay For pioneering many of the ideas at the root of contemporary object-oriented programming languages , leading the team that developed Smalltalk , and for fundamental contributions to personal computing. 2004 Vinton G. Cerf and Robert E. Kahn For pioneering work on internetworking , including the design and implementation of the Internet 's basic communications protocols, TCP/IP , and for inspired leadership in networking. 2005 Peter Naur For fundamental contributions to programming language design and the definition of ALGOL 60 , to compiler design, and to the art and practice of computer programming . 2006 Frances E. Allen For pioneering contributions to the theory and practice of optimizing compiler techniques that laid the foundation for modern optimizing compilers and automatic parallel execution. 2007 Edmund M. Clarke , E. Allen Emerson and Joseph Sifakis For in developing model checking into a highly effective verification technology, widely adopted in the hardware and software industries. 2008 Barbara Liskov For contributions to practical and theoretical foundations of programming language and system design , especially related to data abstraction, fault tolerance, and distributed computing. 2009 Charles P. Thacker For his pioneering design and realization of the Xerox Alto , the first modern personal computer, and in addition for his contributions to the Ethernet and the Tablet PC. 2010 Leslie G. Valiant For transformative contributions to the theory of computation , including the theory of probably approximately correct ( PAC ) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing. 2011 Judea Pearl For fundamental contributions to artificial intelligence through the development of a calculus for probabilistic and causal reasoning . The ACM A.M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) to " an individual selected for contributions of a technical nature made to the computing community ". It is stipulated that " The contributions should be of lasting and major technical importance to the computer field ". The Turing Award is recognized as the " highest distinction in Computer science " and " Nobel Prize of computing ". The award is named after Alan Turing , mathematician and reader in mathematics at the University of Manchester. Turing is "frequently credited for being the Father of theoretical computer science and artificial intelligence ". As of 2007, the award is accompanied by a prize of $250,000, with financial support provided by Intel and Google . The first recipient, in 1966 , was Alan Perlis , of Carnegie Mellon University . Frances E. Allen of IBM , in 2006, was the first female recipient in the award's forty year history. The 2008 award also went to a woman, Barbara Liskov . from : http://en.wikipedia.org/wiki/Turing_Award
2012年6月23日 是 Alan Turing ( 艾伦·图灵 ) 诞辰100周年. 让我们来看看这位传奇人物的一生,其诞辰100年后的今天 他的死 还在 牛津被探讨 ------------------------------------------------------------------------------------- 1, 简介: 艾伦·麦席森·图灵 , OBE , FRS ( 英语 : Alan Mathison Turing ,又译 阿兰·图灵 , Turing 也常翻譯成 涂林 或者 杜林 , 1912年6月23日 -1954年6月7日),是 英国 数学家 、 邏輯學家 , 他被视为 计算机科学 之父。 1931年 图灵进入 剑桥大学国王学院 ,毕业后到美国 普林斯顿大学 攻读 博士 学位, 二战 爆发后回到剑桥,后曾协助军方破解 德国 的著名密码系统 Enigma ,对盟军取得了二战的胜利有一定的帮助。 图灵对于 人工智能 的发展有诸多贡献 ,例如图灵曾写过一篇名为《机器会思考吗?》( Can Machines Think ? )的论文,其中提出了一种用于判定机器是否具有 智能 的 试验 方法,即 图灵测试 。至今,每年都有试验的比赛。此外,图灵提出的著名的 图灵机 模型为现代 计算机 的 逻辑 工作方式奠定了基础。 图灵是著名的 男同性恋 者之一 ,并因为其性倾向而遭到当时的英国政府迫害,职业生涯尽毁。他亦患有 花粉过敏症 。 图灵还是一位 世界级 的长跑运动员 。他的马拉松最好成绩是2小时46分3秒,比1948年 奥林匹克运动会 金牌成绩慢11分钟。1948年的一次跨国赛跑比赛中,他跑赢了同年奥运会银牌得主汤姆·理查兹( Tom Richards )。 2, 他的死今天还是迷 (from BBC news): 图灵诞辰100年后的今天在牛津的一个会议上,图灵专家Jack Copeland 教授对其自杀死因产生怀疑。主要疑点有: 1, 对于离职,图灵是坦然面对的(他心态很好)。Turing's career was at an intellectual high, and that he had borne his treatment "with good humour". 2,图灵有睡觉前吃苹果的习惯,经常吃不完。并且,他死时发现的苹果警察并没有证明有氰化物(毒)。it was Turing's habit to take an apple at bedtime, and that it was quite usual for him not to finish it; the half-eaten remains found near his body cannot be seen as an indication of a deliberate act. Indeed, the police never tested the apple for the presence of cyanide. 3,图灵死之前周五留了便签银行假期回来后要做的事 He had left a note on his office desk, as was his practice, the previous Friday to remind himself of the tasks to be done on his return after the Bank Holiday weekend. 4 图灵一直积极面对对他同性恋倾向的治疗,与朋友邻居相处也好。 In statements to the coroner, friends had attested to his good humour in the days before his death. His neighbour described him throwing "such a jolly party" for her and her son four days before he died. 而关于他死于氰化钾,他做的一个电解有毒物实验正需要氰化钾。他经常做一些不正常的实验,都带有危险性而且他有品尝物品的习惯。 He had been electrolysing solutions of the poison, and electroplating spoons with gold, a process that requires potassium cyanide. Although famed for his cerebral powers, Turing had also always shown an experimental bent, and these activities were not unusual for him. And he was known for tasting chemicals to identify them. 而这可能是他的死因 -- 一次事故! accident 3, 关于其传奇一生,以下来自维基百科: 孩童和年轻时代 图灵的父亲朱利斯·麦席森·图灵( Julius Mathison Turing )是一名英属印度的公务员。 1911年 ,图灵的母亲Ethel在 印度 的Chatrapur怀了孕。他们希望艾伦在 英国 出生,所以回到 伦敦 ,住在 帕丁顿 ( Paddington )。结果就在那里生下了艾伦。父亲的公务员委任使他在艾伦小时候经常来往于英伦和印度。由于担心印度的气候不利于儿童成长,他把家庭留在英伦与朋友同住。图灵很小的时候就表现出他的天才,后来就更加显著。他说他在三个星期里自己学会阅读,而且,就对数字和智力游戏着迷。 六岁的时候,他的父母为他在一间叫圣迈克尔的( St. Michael's )日间学校註了册。女校长很快就注意到他的天才,随后Marlborough学院的许多教育家也注意到这点。 1926年 ,他十四岁的时候转到了在 多塞特郡 ( Dorset )的Sherborne寄宿学校。开学的第一天,刚好遇上了大罢工。图灵决心要赶上第一天的课,于是他独自从 南安普顿 ( Southampton )骑了六十英里的自行车去上学,途中还在一间旅社度过一宵。 图灵天生对科学的喜好并没有给他在Sherborne的老师留下好印象。他们对教育的定义是着重于人文学科而不是科学。虽然如此,图灵继续在他喜欢的学科表现出惊人的能力,还没有学过基础 微积分 的他,就已经能够解答以他年纪来说算是很高深的难题。 1928年 ,在图灵16岁的时候,開始閱讀 阿尔伯特·爱因斯坦 的著作。他不但能够理解,而且能够从一段并没有明示的文字里推导出爱因斯坦的运动定律。 大学和可计算性的工作 國王學院的電腦房現在以圖靈為名 1931年,图灵考入 剑桥大学国王学院 。1934年他以优异成绩毕业。 1935年 因为一篇有关 中心极限定理 的论文当选为国王学院院士。 图灵在他的重要论文《论 可计算数 及其在判定问题上的应用》( 英语 : On Computable Numbers, with an Application to the Entscheidungsproblem )( 1936年 5月28日 提交)里,对 哥德尔 1931年 在证明和计算的限制的结果作了重新论述,他用现在叫做 图灵机 的简单形式裝置代替了哥德尔的以通用算术为基础的形式语言。由于速度很慢,尽管没有一台图灵机会有实际用途,图灵还是证明了这样的机器有能力解决任何可想像的数学难题,如果这些难题是用一种算法来表达。现今,图灵机还是 计算理论 研究的中心课题。他继续证明了 判定问题 ( Entscheidungsproblem )是没有答案的。他的证明首先展示了图灵机的 停机问题 ( halting problem )是没有答案的,这是说不可能用一个算法来决定一台指定的图灵机是否会停机。尽管他的证明比 阿隆佐·邱奇 在 λ演算 方面相等的证明晚发表了几个月,图灵的著作是更易于理解和直观的。 他的通用(图灵)机的概念也是新穎的。这一通用机能够完成任何其他机器所能做的任务。这篇论文还介绍了可定义数的概念。 图灵在 普林斯顿大学 度过了 1937年 和 1938年 的大部分时间,在邱奇指导下学习。 1938年 ,他取得了 博士 学位。他的论文介绍了 超计算 ( hypercomputation )的概念。这里,图灵机给加上了启示器,因而,可以用于研究不能用算法解答的问题。 1939年 图灵回到剑桥,聆听了 维特根斯坦 关于 数学基本原理 ( foundations of mathematics )的讲座。他们激烈地争论,图灵为 形式主义 辩护,而维特根斯坦則认为把数学抬得太高而且不能发现任何绝对真理。 早期的计算机研究:图灵测试 在 布萊切利園 的图灵石像 主条目: 图灵测试 1945年 到 1948年 ,图灵在国家物理实验室,负责自动计算引擎( ACE )的工作 。 1949年 ,他成为 曼彻斯特大学 计算机实验室的副主任,负责最早的真正的计算机---曼彻斯特一号的软件工作。在这段时间,他继续作一些比较抽象的研究,如“计算机械和智能”。图灵在对人工智能的研究中,提出了一个叫做 图灵测试 ( Turing test )的实验,尝试定出一个决定机器是否有感觉的标准。 1952年 ,图灵写了一个 国际象棋 程序。可是,当时没有一台计算机有足够的运算能力去执行这个程序,他就模仿计算机,每走一步要用半小时。他与一位同事下了一盘,结果程序输了。 後來 美国 新墨西哥州 洛斯阿拉莫斯國家實驗室 的研究群根據圖靈的理論,在 ENIAC 上設計出世界上第一個電腦程序的象棋。 图案形成和数理生物学的研究 从 1952年 直到去世,图灵一直在数理生物学方面做研究。他在 1952年 发表了一篇论文《形態發生的化学基础》( 英语 : The Chemical Basis of Morphogenesis )。他主要的兴趣是斐波那契葉序列,存在于植物结构的 斐波那契數 。他应用了反应-扩散公式,现在已经成为图案形成范畴的核心。他后期的论文都没有发表,一直等到 1992年 《艾伦·图灵选集》出版,这些文章才见天日。 迫害和逝世 图灵在 Cheshire East 威姆斯洛 的家,挂有 藍色牌匾 。 因为图灵的 同性恋 倾向而遭到的迫害使得他的职业生涯尽毁。 1952年 ,他的同性伴侣协同一名同谋一起闯进图灵的房子实施盗窃,图灵为此而报警。但是 英国警方 的调查结果使得他被控以“明显的猥亵和性颠倒行为”罪(请参看 鸡奸法 )。他没有申辩,并被定罪。在著名的公审后,他被给予了两个选择:坐牢或 荷尔蒙 “疗法”(即 化学阉割 )。他最后选择了荷尔蒙注射, 并持续一年。在这段时间里,药物产生了包括乳房不断發育的副作用,也使原本热爱体育运动的图灵在身心上受到极大伤害。 1954年 ,图灵因食用浸过 氰化物 溶液的苹果死亡。很多人相信他的死是有意的,并判决他的死是自杀。但是他的母亲极力争辩他的死是意外,因为他不小心在实验室里堆放了很多化学物品(既然是他母亲亲自承认的,那应该属于一个不该的意外)。 苹果公司 的商标有时会被误认为是源于图灵自杀时咬下的半个苹果 ,但该图案的设计师 和苹果公司都否认了这一说法 。 平反 在 2009年 9月10日 ,一份超过3万人的請愿签名,使 英国首相 戈登·布朗 在《 每日電訊報 》撰文,因為 英國政府 當年以同性戀相關罪名起訴圖靈並定罪,導致他自殺身亡,正式向艾伦·图灵公開道歉。 至2012年,有21000多人签名请愿,要求英国政府追赠图灵死后赦免状,但被当局拒绝。 英國上議院 的McNally勋爵解释说,死後赦免状是不合适的,因为图灵是根据当时的法律被定罪。
最早认识到“goto有害” 1 972年的图灵奖授予荷兰的计算机科学家埃德斯加·狄克斯特拉(Edsgar Wybe Dijkstra)。狄克斯特拉因为最早指出“goto是有害的”以及首创结构化程序设计而闻名于世。事实上,他对计算机科学的贡献并不仅仅限于程序设计技术,在算法和算法理论,编译器,操作系统诸多方面狄克斯特拉都有很多创造,做出了杰出贡献。1983年,ACM为了纪念Communicaion of ACM创刊25周年,评选出从1958年--1982年的四分之一世纪中在该杂志上发表的25篇有里程碑意义的论文,每年一篇,狄克斯特拉一人就有两篇入选,是仅有的这样的两位学者之一(另一位是英国学者霍尔 C.A.R. Hoare)。 狄克斯特拉1930年5月11日生于鹿特丹的一个知识分子家庭,在兄弟姊妹4人中排行第三。他的父亲是一名化学家和发明家,曾担任荷兰化学会主席。他母亲则是一位数学家。狄克斯特拉的少年时代是在德国法西斯的铁蹄下度过的。由于食物短缺,他被送到乡下他父亲的一个朋友那里去。纳粹德国投降后,1945年7月,十分虚弱的狄克斯特拉才和家人重新团聚。狄克斯特拉原打算学法律,毕业后到联合国工作,为维护世界和平服务。但他中学毕业时,数理化成绩都特别好,因此他父亲说服了他,1948年进莱顿大学学习数学和物理。在学习理论物理的过程中,狄克斯特拉发现了这个领域中的许多问题都需要进行大量复杂的计算,于是决定学习计算机编程。1951年,他自费赴英参加剑桥大学举办的一个程序设计培训班,学习在EDSAC上的编程方法,这使他成为世界上第一批程序员之一。第二年,阿姆斯特丹数学中心了解到这一情况,拟聘他为兼职程序员。狄克斯特拉开始时有些犹豫,因为世界上当时还没有“程序员”这一职业。数学中心的计算部主任、Algol语言的设计者之一、荷兰的计算技术先驱维京格尔藤(A.van. Wijingaarden)对他说,目前程序设计虽然还没有成为学科,不被重视,但既然计算机已经有了,正处于开创阶段,你未来就有可能使程序设计成为一个受尊敬的学科。这段话说动了狄克斯特拉,使他接受了这个职位,而且越干越有兴趣,这样,他在第二年就结束了在莱顿大学的学业,成为数学中心全日制的工作人员,从此进入计算机领域,并且正如维京格尔藤所预言的那样,逐渐成为该领域的知名专家,创造出了许许多多的“第一”。 1956年,他成功的设计并实现了在有障碍物的两个地点之间找出一条最短路径的高效算法,这个算法被命名为“狄克斯特拉算法”,解决了机器人学中的一个十分关键的问题,即运动路径规划问题,至今仍被广泛应用。 1959年,在数学中心将他们原先的ARMAC计算机进行升级的过程中,狄克斯特拉设计了一种处理程序,成功的解决了“实时中断”(real-time interrupt)问题。狄克斯特拉的博士论文就是以此为课题完成的,并在阿姆斯特丹大学通过论文答辩而获得博士学位。 1960年8月,Algol60文本推出刚刚半年多,狄克斯特拉和他在数学中心的同事仲纳凡尔特(J.A.Zonneveld)一起就率先实现了世界上第一个Algol60编译器,比欧美其他各国学者实现Algol60早一年还多。这一成就引起各国计算机学者的惊叹,并因此奠定了狄克斯特拉作为世界一流计算机学者在科学界的地位。 1962年,狄克斯特拉离开数学中心进入位于荷兰南部的艾恩德霍芬技术大学(Eindhove Technical University)任数学教授。在这里,他参加了X8计算机的开发,设计与实现了具有多道程序运行能力的操作系统--THE Multiprogramming System。THE是艾恩德霍芬技术大学的荷兰文Technische Hoogeschool Eindhoven的词头缩写。狄克斯特拉在THE这个系统中所提出的一系列方法和技术奠定了计算机现代操作系统的基础,尤其是关于多层体系结构,顺序进程之间的同步和互斥机制这样一些重要的思想和概念都是狄克斯特拉在THE中国首先提出并为以后的操作系统如UNIX等所采用的。为了在单处理机的情况下确定进程(process)能否占有处理机,狄克斯特拉将每个进程分为“就绪”(ready)、“运行”(running)和“阻塞”(blocking)三个工作状态,由于在任一时刻最多只有一个进程可以使用处理机,正占用着处理机的进程称为“运行”进程。当某进程已具备了使用处理机的条件,而当前又没有处理机供其使用,则使该进程进入“就绪”状态。当运行进程由于某种原因无法继续运行下去时,就停止其占用处理机,使之进入“阻塞”状态,待造成其退出运行的条件解除,在进入“就绪”状态。而对系统中所有同时运行的进程之间所存在的相互制约的同步(Synchronization,指为了避免错误,在一个进程访问共享数据时,另一个进程不访问该数据)和互斥(mutaullu exclusive,指两个进程不能同时在一个临界区中使用同一个可重复使用的资源,诸如读写缓冲区)两个关系,狄克斯特拉巧妙的利用火车运行控制系统中的“信号灯”(semaphore,或叫信号量)概念加以解决。所谓信号量,实际上就是用来控制进程状态的一个代表某一资源的存储单元。例如,P1和P2是分别将数据送入缓冲B和从缓冲B读出数据的两个进程,为了防止这两个进程并发时产生错误,狄克斯特拉设计了一种同步机制叫“PV操作”,P操作和V操作是执行时不被打断的两个操作系统原语。执行P操作P(S)时信号量S的值减1,若结果不为负则P(S)执行完毕,否则执行P操作的进程暂停以等待释放。执行V操作V(S)时,S的值加1,若结果不大于0则释放一个因执行P(S)而等待的进程。对P1和P2可定义两个信号量S1和S2,初值分别是1和0.进程P1在向缓冲B送入数据前执行P操作P(S1),在送入数据后执行V操作V(S2)。进程P2在从缓冲B读出数据前先执行P操作P(S2),在读出数据后执行V操作V(S1)。当P1往缓冲B送入以数据后信号量S1的值变为0,在该数据读出后S1的值才又变为1,因此在前一数未读出前后一数不会送入,从而保证了P1和P2之间的同步。我国读者常常不明白这一同步机制为什么叫PV操作,原来这是狄克斯特拉用荷兰文定义的,因为在荷兰文中,通过叫passeren,释放叫vrijgeven,PV操作因此得名。这是在计算机术语中不是用英语表达的极少数例子之一。 THE还有许多特色和创新,如: 1. 对短程序予以特殊处理,以减少其周转时间,从而提高整个系统的效率; 2. 在使用外围设备方面采取了一系列特殊手段,使之更加经济; 3. 对与CPU相联的后援存储器能进行自动控制; 4. 设计中既考虑了方便程序员使用,也考虑了方便操作员使用和维护计算机系统。 THE是在程序设计中最先引入并发概念的系统,开创了并发程序设计的先河。因此,当1967年,狄克斯特拉在ACM召开的第一届操作系统原理讨论会上提交的论文“THE 多道程序系统的结构”一文中介绍了该系统后,引起了与会者的极大兴趣和重视。该文后来刊载于1968年5月的Communication of ACM上,就是被评为有里程碑意义的25篇论文之一。狄克斯特拉的另一篇有里程碑意义的论文是“并发程序控制中的一个问题的解决”(Solution of a Problem in Concurrent Programming Control),是1965年9月发表的。 1968年3月,Communication of ACM登出了狄克斯特拉的那封影响深远的信,在信中他根据自己编程的实际经验和大量观察,得出如下结论:一个程序的易读性和易理解性同其中所包含的无条件转移控制的个数成反比关系,也就是说,转向语句的个数愈多,程序就愈难读、难懂。因此他认为“GOTO是有害的”,并从而启发了结构化程序设计的思想。1972年,他与当时在爱尔兰昆士大学任教的英国计算机科学家、1980年图灵机获得者霍尔合著了《结构化程序设计》一书(Structure Programming, Academic Pr.),进一步发展与完善了这一思想,并且提出了另一个著名的论断:“程序测试只能用来证明有错,决不能证明无错!”(Program testing can be used to show the presence of bugs, but never to show their absence!)。 1973年8月,狄克斯特拉离开了艾恩德霍芬,应聘担任著名的美国宝来公司(Burroughs)的高级研究员,但宝来并不要求他到密西根州的底特律总部或世界各地的任一分支机构去上班,而是给予他最大的自由:留在荷兰家里做自己感兴趣的任何事情,或到世界各地旅行、考察、参加会议......唯一的要求是他经常把自己的行踪、见闻、观感、心得和看法以书面形式向公司报告。狄克斯特拉于是当了约10年的“自由”研究员,这期间他去过德国、英国、安哥拉、瑞士、加拿大、波兰、苏联、日本、法国、澳大利亚等许多国家,参加了许多学术会议、讨论会或培训班,当然也继续做许多研究工作。这期间,狄克斯特拉对计算机科学做出的最重要的贡献,就是1975年他提出了公理化语义描述的一种方法,叫“最弱前置条件方法”(weakest pre-condition method),这种方法是在霍尔所提出的前后断言(assertion)的基础上形成的。其基本思想是:将程序设计看做是“面向目标”的活动,编程就是从预先给定的“后断言”出发,逆向的逐步推导出满足它的程序,同时计算出所需的最弱前置条件。它是一个谓词公式,用wp(S,R)表示,其中R是语句S执行后所期望的结果,也就是后断言或称结果断言。例如,赋值语句(assignment statement)的语义可如下表示: wp(x:=e,R)=R 其意义是将R中x的所有自由出现同时代换成e。 假定将x*x赋给x后,x^4=10,则可表示成: wp("x:=x*x", x^4=10)=((x*x)^4=10)=(x^8=10) 为了证明循环的终止性,狄克斯特拉引入了循环不变式和界函数。一般说来,一个循环呈如下形式: |invariant:P| --进入循环前,不变式P真, |bound:t| --并且B真时t0,t是循环次数的上界 doB-Decrease t, S true od --当B真时,使t递减并执行S,S执行过程真 保持P |P^B| --则循环必然终止且终止时P真B假 若Q是S的执行能在有限时间内终止并满足R的任一前提条件,则必有Q=wp(S,R)。因此,证明前后断言Q{S}R只需先求出最弱前置断言wp(S,R),再证明Q=wp(S,R)。 当给定了Q和R,根据Q,R的结构,通过推导wp(S,R),可推出S的结构,从而将程序设计过程变成了数学推导的过程。 狄克斯特拉所提出的最弱前置条件的概念及相应的程序设计演算,使得程序设计和程序验证可同时进行,具有十分重要的理论意义和实际价值,极大地促进了程序设计作为科学的进程。 狄克斯特拉于1984年结束了宝来公司的自由研究员的生活,应邀出任位于奥斯汀的德克萨斯大学计算机科学系名誉主任。 狄克斯特拉论著极多,主要有: 《Algol 60程序设计入门》(A Primer of Algol 60 Programming,Academic Pr., 1962) 《程序设计的训练方法》(A Discipline of Programming, Prentice-Hall, 1976) 《程序设计的教学就是思维方法的教学》(The Teaching of Pro-gramming i.e. the Teaching of Thinking, Springer, 1976) 《关于计算的论著选集:个人的观点》(Selected Writing on Computing: A Personal Perspective, Springer, 1982) 《程序设计方法》(A Method of Programming, Addison-Wesley,1988) 《程序与证明的形式开发》(Formal Development of Programs and Proofs, Addison-Wesley, 1990) 《谓词演算与程序语义》(Predicate Calculus and Program Semantics, Springer, 1990) 除了图灵奖,狄克斯特拉还在1974年获得AFIPS的Harry Goode奖。 狄克斯特拉是在1972年8月14日于波士顿召开的ACM年会上接受图灵奖的。他发表了题为“智力低下的程序员”(The Humble Programmer)的图灵奖演说,刊于Communication of ACM,1973年10月,859~866页。也可见于《前20年的ACM图灵奖演说集》(ACM Turing Award Lectures-The First 20 Years:1966-1985, ACM Pr.)17~32页。演说中他肯定了Fortran, Algol, LISP等语言,而对于PL/I,他认为是失败的。演说的重点是如何建立可靠的软件,如何在编程时就尽力避免引入错误,而不是以后再去消除错误,这不单是具有技术上的意义,而且在经济上十分重要。狄克斯特拉的上述观点赢得了愈来愈多的人的理解和支持。 延伸阅读--http://amturing.acm.org/award_winners/dijkstra_1053701.cfm
Creating the Impossible是工业光魔的口号,借用一下。我们想创造的皇帝新脑,目前也是一种 impossible 。 在博文《 想象力是有限的,人脑可能根本不能认识mind! 》中,提到了人脑的局限性,可能不能理解mind怎么从物质运动中产生。Mcginn提出用基因改造的方法,改造人脑。这可能有一定的可行性,但涉及到伦理问题,是不能实施的 。而且,在神经生物的物质基础上,人脑可能已经是最优化的了 。我们的教科书经常说人脑比猴子、猩猩大,智力水平高,但智力的水平并不是简单地依赖脑的大小或者神经元的多少。陆地上,蜂鸟的脑很小,但很聪明,大象的脑够大了,但智力水平可能还不如蜂鸟!海洋里,海豚是非常聪明的,甚至有人猜测他们都已经形成文化了,只是没有手建造出来,而鲸鱼的脑够大了吧,但聪明程度还不如海豚。脑变大,是有信息交换速度的代价的,神经电冲动从一个脑区的传导到另一个远离的脑区,需要时间和能量代价。能量可能是一个重要的约束条件,脑里的能量主要消耗在神经点传导中Na和K离子的主动运输上,以及突触连接部位,递质的释放和回收上。神经元越密集,突起长度越长,突触连接越多,消耗的能量也越大。依靠血液运输能量,是有限制的。因此,单纯地改造基因,进而改造脑,可能也是一种效果有限的办法。 我的看法类似强人工智能,认为人的思维也是一种计算 。mind不过是物质运动的过程,这个过程能够表征(represent)一些概念,所有的思维不过是对其他事物的一种表征。现有的计算程序有很多符号,也可以看作对其他事物的一种表征。但我理解的“计算”和目前的计算机工作是有很大差别的,只不过找不到更好的词描述,只能用这个词了。目前的计算机都是冯诺依曼架构的,基于存储程序的原理。每一个动作都需要预先设定好,按照既定的方案进行反应,这种死板的动作,造成所有结果都是可以预知的,明显是不可能有“自己”的想法或者说自由意志的。我们每天吃进去的,也都是普通的物质,脑也是由普通的物质构成的,并没有什么特殊的元素。那我们只要以一定的方式组织普通的物质,我相信还是可以创造出有智能的“机器”的。关键是要理解脑区别于其他物体的特有属性,根据这些属性,创造出具备这些属性的“机器”,才可能有mind emerge出来。根据我对脑科学的认识,认为至少有一下几点: 1. 可塑性 。生物体是不断变化的,脑也一样 。变化的东西才能成长,才能学习,才能认识。所以,这个“机器”应该是动态改变的。 2. 反馈、调整 。脑不仅能够理解外界输入的信号,而且还能根据信号,改造自身。这种改造不仅是软件上的,比如形成记忆,学习到技能,更重要的是硬件上的,脑本身结构上的改变,比如树突棘可以在几个小时内生长消亡 。这个“机器”也应该能根据输入信号改变自身,包括软件和硬件!现在的人工神经网络,特别是B-P 神经网络,就是一种通过反馈来改变调整网络中的权重,模拟脑神经的这种特性,才达到学习的能力的。但这种改变仍然只是软件上的,虽然有人在硬件上设计人工神经网络(我一个高中同学在中科院就是研究这个的),也仍然是根据反馈改软件,我还没有看到有改变硬件电路本身的研究。 3. 处于 混沌的临界状态 ,在有序和无序边缘。脑是一种高度结构化的组织,特别是神经元的分布和突起连接,比如皮层就分为六层(近年也有说7层的),每一层都有特异性的结构,发挥特别的作用,一般第四层是接收丘脑投射进来的神经信号,二三层主要是做内部信息处理,第五层的椎体细胞的轴突很长,把信息投射出去,到达特异的脑区或身体部位。这种结构的特异性并不代表稳定性,而是不断变化的,就是处于一种稳定的边缘。这个观点是浦大师说的,他人工培养神经元,形成网络,并分析网络的响应和学习特性。人工培养的神经网络就处于这么一种状态。 4. 模拟信号和数字信号融合 。日常生活中,声音和光线应该可以看作模拟信号,脑的输入也就是模拟信号。但转换成神经电信号的时候,似乎有一个模数转换的过程!神经电冲动是有一个阈值的,累积的电势达到阈值后,才会爆发一个神经冲动,就像一个离散化的过程,曲线见下图。显然目前的计算机都是数字信号,缺乏模拟信号的真实性。做过硬件电路的都知道,模拟电路是很难做的。 图片来自 Wiki 目前的技术水平来看,上述条件还是很难满足的,期待技术的突破。如果做出来了,从外观和行为上,也能表现得像有意识,我们能下结论说job done吗? 怎么判断一个事物是否有意识?由于意识的孤立性,没有交集,所以无法直接与mind沟通,还是只能通过外部测试的方式。对这个问题,图灵(Alan Turing) 提出了图灵测试(Turing test)的方法,判断一个机器是否有意识。为了避开外观和行为的差异,把“机器”隔离开,由很多人和“她”用文字聊天,就像聊QQ,聊什么内容可以自由发挥,最后判断和你聊天的是不是一个人 。如果一台“机器”表现得和人一样,就认为通过了图灵测试,具备了mind。这是目前通用的检验方法,但Mcginn提出了异议 ,我很赞同。他有两点理由: 1. 太语言化。聊天的方式要求这个机器语言能力很强,不仅精通英语,还要懂其他语言,条件过于苛刻了。一只猫应该算有意识的,但肯定不能通过这个测试。 2. 行为表现不能证明内在是否有意识。大家可以设计复杂的语言程序,表现得像一个人在聊天,就像清华大学图书馆的小图一样,但实际上,我们可以认为这种数字化的程序结果,是没有自由意志的。 目前,仍然缺乏一个完美的可行的检验方法。 Alan Turing 参考资料: Mcginn C. The Mysterious Flame: Conscious Minds In A Material World . Basic Books, 2000. Fox D. The limits of intelligence . Scientific American, 2011, 305(1): 36–43. 史蒂芬 霍金, 许明贤. 时间简史——从大爆炸到黑洞 . 长沙: 湖南科学技术出版社, 2001. 彭罗斯, 许明贤, 吴忠超. 皇帝新脑 . 湖南科学技术出版社, 1998. Woolf C J, Salter M W. Neuronal plasticity: increasing the gain in pain . Science, 2000, 288(5472): 1765–1768. Xu T, Yu X, Perlik A J, et al. Rapid formation and selective stabilization of synapses for enduring motor memories . Nature, 2009, 462(7275): 915–919. Turing A M. Computing machinery and intelligence . Mind, 1950, 59(236): 433–460. Hodges A. Beyond Turing’s Machines . Science, 2012, 336(6078): 163–164. Nature最近出了一个专题,介绍Turing的贡献和影响 。 Turing at 100: Legacy of a universal mind TuringHub.com - take a Turing Test . . http://www.turinghub.com/. 一个图灵测试的网站,有兴趣的可以试试 Creating the Impossible ! 工业光魔的传说
2008年我就发现Pearl教授的工作非常迷人,并向Roland推荐过,看来我学术的欣赏品位和对女人的欣赏品位一样好:) Judea Pearl United States – 2011 CITATION For fundamental contributions to artificial intelligence through the development of a calculus for probabilistic and causal reasoning. ACM DL Author Profile Research Subjects Judea Pearl is a professor of computer science at the University of California, Los Angeles, where he was director of the Cognitive Systems Laboratory. Before joining UCLA in 1970, he was at RCA Research Laboratories, working on superconductive parametric and storage devices. Previously, he was engaged in advanced memory systems at Electronic Memories, Inc. Pearl is a graduate of the Technion, the Israel Institute of Technology, with a Bachelor of Science degree in Electrical Engineering. In 1965, he received a Master’s degree in Physics from Rutgers University, and in the same year was awarded a Ph.D. degree in Electrical Engineering from the Polytechnic Institute of Brooklyn. Among his many awards, Pearl is the recipient of the 2012 Harvey Prize in Science and Technology from the Technion, and the 2008 Benjamin Franklin Medal in Computers and Cognitive Science from the Franklin Institute. He was presented with the 2003 Allen Newell Award from ACM and the AAAI (Association for the Advancement of Artificial Intelligence). His groundbreaking book on causality, Causality: Models, Reasoning, and Inference , won the 2001 Lakatos Award from the London School of Economics and Political Science “for an outstanding significant contribution to the philosophy of science.” Pearl is a member of the National Academy of Engineering and a Fellow of AAAI and the Institute for Electrical and Electronic Engineers (IEEE). He is President of the Daniel Pearl Foundation www.danielpearl.org named after his son. Pearl's Work Judea Pearl's work has transformed artificial intelligence (AI) by creating a representational and computational foundation for the processing of information under uncertainty. Pearl's work went beyond both the logic-based theoretical orientation of AI and its rule-based technology for expert systems. He identified uncertainty as a core problem faced by intelligent systems and developed an algorithmic interpretation of probability theory as an effective foundation for the representation and acquisition of knowledge. Focusing on conditional independence as an organizing principle for capturing structural aspects of probability distributions, Pearl showed how graph theory can be used to characterize conditional independence, and invented message-passing algorithms that exploit graphical structure to perform probabilistic reasoning effectively. This breakthrough has had major impact on a wide variety of fields where the restriction to simplified models had severely limited the scope of probabilistic methods; examples include natural language processing, speech processing, computer vision, robotics, computational biology, and error-control coding. Equally significant is Pearl's work on causal reasoning, where he developed a graph-based calculus of interventions that makes it possible to derive causal knowledge from the combined effects of actions and observations. This work has been transformative within AI and computer science, and has had major impact on allied disciplines of economics, philosophy, psychology, sociology, and statistics.
Turing Year in China The Turing Lectures 16-21 May 2012 Beijing, China Institute of Software (ISCAS) Chinese Academy of Sciences ISCAS at the Software Park in Beijing Turing Lecturers S Barry Cooper (Leeds, Chair Turing Centenary Committee) John Hopcroft (Cornell, 1986 Turing award winner) Richard M. Karp (Berkeley, 1985 Turing Award Winner) Jon Kleinberg (Cornell, 2006 Nevanlinna Prize) Butler W. Lampson (Microsoft, 1992 Turing Award Winner) Li Deyi (Chinese Academy of Engineering, Beijing, China) Wei Li (BUAA, Beijing, China) Andrew Chi-Chih Yao (Tsinghua, 2000 Turing Award Winner) Organizing Chairs for the Turing Lectures 2012: John Hopcroft (Cornell) Angsheng Li (ISCAS) Organizing Committee for the Turing year in China: George Barmpalias (ISCAS) Barry S. Cooper (Leeds) John Hopcroft (Cornell) Angsheng Li (ISCAS, co-chair ) Yucheng Li (ISCAS, co-chair ) Huimin Lin (ISCAS) Pengzhi Liu (Renmin Highschool, co-chair ) Zhiyong Liu (ICT, CAS) Ruqian Lu (Math Academy, CAS) Jian Zhang (ISCAS) Chaochen Zhou (ISCAS) Local organizing Committee for the Turing year in China: George Barmpalias (ISCAS) Yunfu Cao (ISCAS) Haiming Chen (ISCAS) Zhiming Ding (ISCAS) Angsheng Li (ISCAS, co-chair ) Yucheng Li (ISCAS, co-chair ) Dongdai Lin (ISCAS) Kelong Liu (ISCAS) Hongan Wang (ISCAS) Mingji Xia (ISCAS) Ye Yang (ISCAS) Yongji Wang (ISCAS) Naijun Zhan (ISCAS)
今年是阿兰•麦席森•图灵(Alan Mathison Turing,1912-1957)的百年祭。图灵是英国著名的数学家和逻辑学家,被称为计算机科学之父、人工智能之父,是计算机逻辑的奠基者,提出了“图灵机”和“图灵测试”等重要概念。人们为纪念其在计算机领域的卓越贡献而设立“图灵奖” 为了纪念这位伟大的科学家,中国科学院软件所将在五月份举办题为“第九届计算模型的理论与应用大会”(9th Annual Conference on Theory and Applications of Models of Computation)。此次会议的目的是“把广大研究人员有关计算理论与应用的兴趣聚拢起来,其主旨在于探讨可计算性、复杂性以及算法,同时顾及这些成果向信息与网络的延伸。”究竟有多广泛呢?我们可以从会议罗列的题目中管窥一斑,当然其范围还远远不限于此: 算法代数(Algorithmic algebra,) 算法图论与组合组合数学(Algorithmic graph theory and combinatorics) 算法与数据结构(Algorithms and data structures) 近似算法(Approximation algorithms) 自动机和神经网络(Automata and neural networks) 计算生物学和生物信息学(Computational biology, and bio-informatics) 计算复杂性(Computational complexity) 计算博弈论、网络博弈论(Computational game theory, network game theory) 计算几何(Computational geometry) 可计算数学(Computable mathematics) 连续和实运算(Continuous and real computation) 密码学和复杂性(Cryptography and complexity) 可判定下和不可判定性(Decidability and undecidability) 解随机化(Derandomization) 错误校正和局部可测编码(Error correcting code and locally testable codes) 互联网数学(Internet mathematics) 学习理论和智能计算(Learning theory, and intelligent computing) 数学性质的局部测试(Local test of mathematical properties) 计算和网络模型(Models of computing and networking) 自然计算(Natural computation) 网络算法(Network algorithms) 构建网络(Networking) 自然与社会网络-新法则和原则(Networks in nature and society - new laws and principles) 数论与编码理论(Number theory and coding theory) 在线算法和并行算法(On-line algorithms and parallel algorithms) 物理可计算性(Physical computability) 程序检查(Programm checking) 证明与计算(Proofs and computation) 量子计算(Quantum computing) 随机化算法(Randomized algorithms) 复杂类与自然中的随机性(Randomness in complexity classes and in nature) 相对可计算性和等级结构Relative computability and degree structures 网络的鲁棒性与安全性 (Robustness and security of networks) 网络与突现的理论Theory of networks and emergence 图灵可定义性(Turing definability)
今年的6月23日,计算机专业童鞋的祖师爷爷图灵先生百岁诞辰,这是一个大日子,大日子自然要有大动作了,这不,23日的Nature出专刊来纪念祖师爷爷了- Nature ( 23 February 2012 ) 。 http://www.nature.com/news/specials/turing/index.html 这一期special的doodle做的最漂亮:图灵头像居中,左右两边的圆圈代表了图灵机中无限长的纸带,右下角是根据图灵机模型做出的真实计算机,左下角的潜艇代表了图灵二战期间为英国军方服务的历史。 Nature这一期的专刊共有10篇文章,其中 两篇 Features : Turing at 100: Legacy of a universal mind Computer modelling: Brain in a box 七篇 Opinion : Turing at 100 The man behind the machine Turing centenary: The dawn of computing Turing centenary: Life's code script Turing centenary: Is the brain a good model for machine intelligence Turing centenary: Pattern formation Turing centenary: The incomputable reality 还有一篇 Futures : Ghost in the machine 个人感觉七篇Opinion文章中的很多观点说的好极了,总结下来有这么几个亮点: 1. 百年之际,图灵值得关注 2. 图灵为逻辑学和机器之间架起了一座桥梁,这为现代计算机奠定了基础 3. 当下的时代里,图灵的声誉极高;但在一九四五十年代的时候他并不出名,其巨大贡献在其死后也长期被人忽视,大家只是因为他有所谓的“丑闻”而知道他,这种reputation 从zero到hero的变化难道不值得我们思考吗? 4. 生命中的细胞和图灵机具有很多的相似之处 5. 图灵机对于生物过程中的形态演化的影响巨大,但我们才刚刚认识到 6. 脑科学和计算机科学之间的巨大鸿沟还需要我们这些图灵的徒子徒孙们好好弥补 7. 世界中的广泛互联性是值得关注的一个热点,请看看Facebook的巨大成功吧 OK,介绍到此为止,具体的内容还是请大家去看Nature的原文吧
智能系统至少涉及人脑智能系统、电脑智能系统和(双脑)协同智能系统。 塞尔“中文屋子”是针对“是否通过‘图灵测试’就算具有智能?”的一个否定性回答。其实质是说明:人脑智能系统(强人工智能假设)与电脑智能系统(弱人工智能假设)之间的区别。 The Chinese Room (中文屋子)Argument Searle and the Chinese Room Argument http://www.mind.ilstu.edu/curriculum/modOverview.php?modGUI=203 http://en.wikipedia.org/wiki/Chinese_room http://www.iep.utm.edu/chineser/ http://plato.stanford.edu/entries/chinese-room/ http://plato.stanford.edu/entries/turing-test/ http://plato.stanford.edu/entries/turing-machine/ 附录1: The Chinese Room Argument In your work on the mind and the brain you talk about how there is always a turn in an era to a metaphor that is dominant in technology, hence the dominant one now is to say that the mind is like a computer program. And to answer that you've come up with the "Chinese Room." Tell us a little about that. Well, it's such a simple argument that I find myself somewhat embarrassed to be constantly repeating it, but you can say it in a couple of seconds. Here's how it goes. Whenever somebody gives you a theory of the mind, always try it out on yourself. Always ask, how would it work for me? Now if somebody tells you, "Well, really your mind is just a computer program, so when you understand something, you're just running the steps in the program," try it out. Take some area which you don't understand and imagine you carry out the steps in the computer program. Now, I don't understand Chinese. I'm hopeless at it. I can't even tell Chinese writing from Japanese writing. So I imagine that I'm locked in a room with a lot of Chinese symbols (that's the database) and I've got a rule book for shuffling the symbols (that's the program) and I get Chinese symbols put in the room through a slit, and those are questions put to me in Chinese. And then I look up in the rule book what I'm supposed to do with these symbols and then I give them back symbols and unknown to me, the stuff that comes in are questions and the stuff I give back are answers. Now, if you imagine that the programmers get good at writing the rule book and I get good at shuffling the symbols, my answers are fine. They look like answers of a native Chinese . They ask me questions in Chinese, I answer the questions in Chinese. All the same, I don't understand a word of Chinese. And the bottom line is, if I don't understand Chinese on the basis of implementing the computer program for understanding Chinese, then neither does any other digital computer on that basis, because no computer's got anything that I don't have. That's the power of the computer, it just shuffles symbols. It just manipulates symbols. So I am a computer for understanding Chinese, but I don't understand a word of Chinese. http://globetrotter.berkeley.edu/people/Searle/searle-con4.html 附录2 : 十个著名悖论的最终解答(八)中文房间(The Chinese Room) 引用: “中文房间”最早由美国哲学家John Searle于20世纪80年代初提出。这个实验要求你想象一位只说英语的人身处一个房间之中,这间房间除了门上有一个小窗口以外,全部都是封闭的。他随身带着一本写有中文翻译程序的书。房间里还有足够的稿纸、铅笔和橱柜。写着中文的纸片通过小窗口被送入房间中。根据Searle,房间中的人可以使用他的书来翻译这些文字并用中文回复。虽然他完全不会中文,Searle认为通过这个过程,房间里的人可以让任何房间外的人以为他会说流利的中文。 解读: Searle创造了“中文房间”思想实验来反驳电脑和其他人工智能能够真正思考的观点。房间里的人不会说中文;他不能够用中文思考。但因为他拥有某些特定的工具,他甚至可以让以中文为母语的人以为他能流利的说中文。根据Searle,电脑就是这样工作的。它们无法真正的理解接收到的信息,但它们可以运行一个程序,处理信息,然后给出一个智能的印象。 引用完毕。 “中文房间”问题足够著名,这是塞尔为了反击图灵设计的一个思想实验。 机器可以有思想吗?这是一个老的不能再老的问题。图灵问:“有思想”是什么意思?我说它有思想,你不承认怎么办?我们怎么判断一台机器是不是有思想? 于是图灵设计了一个“图灵测试”,图灵认为这是一个可操作的标准——如果机器通过了这个测试,我们就应当承认它有思想。 图灵测试是这样的:把一个等待测试的计算机和一个思维正常的人分别关在两间屋子里,然后让你提问题,你通过提问,通过分析机器和人对你的问题的回答来想办法区分哪一个是机器,哪一个是人。如果你无法区分,那么,这台机器就通过了测试,就证明这台机器和人一样具有思维,有思想——这是一台会思考的机器。 塞尔用中文房间这个思想试验反击图灵——事实上这确实彻底击溃了图灵。 中文房间应当这样说才是正确的:一个不懂中文的人(西方人认为中文就像天书一样难以理解,如果他认为你的话难以理解,就会说:你说的简直就是中文!)被关在一间封闭的屋子里,屋里有一个完整的中文对照表——任何一个中文句子都对应一个其他的句子,事实上对应的那个句子是前一个句子的答案。你可以用中文向这个人提问,问题写在一张纸条上传给这个人,这个人只要查找对照表,找到对应的中文句子传出来就行了。那么,这个完全不懂中文的人,确实像一个精通中文的一样回答一切中文问题,但是他丝毫不“知道”任何一句话的意思。 在此基础上,有人提出了更强烈的反击:把爱因斯坦对任何一个问题的回答汇编成一本书,那么你拿任何一个问题去问爱因斯坦,与翻着本书会得到同样的答案,现在我们能说这本书像爱因斯坦一样会思考吗? 所以转了一大圈,我们还是要回过头来重新审视前面说过的第二个悖论——空地上的奶牛,要重新审视柏拉图的JTB:什么是“知道”?“知道”是什么意思? http://www.tianya.cn/techforum/content/666/9815.shtml
2012年的6月23日,将迎来图灵100岁诞辰。届时,全球计算机界必将掀起盛大的纪念活动。鄙人作为小角色自然没资格去参加那些大腕们的高层次聚会了。因此只好赶个大早,躲在角落处提前撰文,以此来纪念计算机界的鼻祖--图灵先生。 图灵先生的照片来自网络 阿兰.图灵(Alan Turing),1912年出生在英国伦敦周边一个名叫曼达威尔的小镇。他从小爱好数学,后来考入剑桥大学,他读大学时展现了其优秀的数学天赋,获得了数学奖学金,并于1938年在普林斯顿大学获得博士学位。图灵博士毕业后回到英国,继续从事数理逻辑方面的研究工作。二战爆发后,他协助英国军方进行通信方面的工作,并成功的破解了德国纳粹的军事密码。 在1936年,图灵的经典论文《关于可计算数,及其在决策问题中的应用》( Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem" . Proceedings of the London Mathematical Society . 2 42 : 230–65. 1936–37. ),公开发表,此文提出了“图灵机”的概念,将一个数学问题是否可解,最终等价为“图灵机”是否停机的问题。(关于“图灵机”的具体概念,可以参考郝克刚教授的博文) 这篇经典的论文,为计算机的制造,奠定了理论基础。也正是因为图灵的伟大贡献,计算机界的最高奖项被命名为“图灵奖”。 鄙人作为计算机行业的一名小学生,始终认为 图灵先生是最伟大 的。何为伟大? 伟大就是做出了巨大的成就,而并不为人所注意,我们普通人享受着他的伟大成果,却甚至都没有感受到他的存在 。我在此敲击的键盘,看着计算机显示器上的字符图画,尽情在网络上挥洒着自己的想法,但什么时候会去细想这计算机的工作细节,什么时候会去思考奠定计算机工作原理的图灵机是怎么被发明出来的。估计像我一样的绝大多数博友们都在享用着计算机和网络的好处,却早已忽略了图灵的存在了..... 想想我们脚下的大地;天上的太阳;以及呼吸的空气吧。我们时时刻刻的享受着她们,却甚至早已忽略了她们的存在。我们甚至肆意的毁坏蹂躏她们,却甚至将她们对我们的宽厚包容视为软弱可欺。 大地、阳光、空气,这难道不是最伟大的东西吗? 图灵先生是在1954年去世的,死时年仅41岁。普遍的说法是因为他误食了沾有氰化钾的毒 苹果 ,而死亡的具体细节在学术史界还有争论。人们在惋惜他英年早逝之余,也不禁感叹: 看来苹果真的是会造就伟人的,无论是亚当和夏娃偷吃的那一个,砸中牛顿头的那一个,还是被乔布斯咬了一口的那一个......
图灵( Alan Turing )的伟大贡献 -- 纪念图灵诞辰 100 周年( 7 ) 西北大学 郝克刚 7) 图灵测试,计算机的智能 电子计算机诞生以后,人们惊奇地发现它的能力大大超出原来的预期。计算机不仅可以做大量的计算,还能进行复杂的推理。于是就把它同人的大脑进行比较,提出“计算机能思维吗”的问题。这里涉及到对“什么是思维”的理解和界定,涉及哲学、认知学以及社会学等各个方面,相当复杂众说纷纭,很难有一个统一的标准。图灵 1950 年 10 月在英国曼彻斯特大学发表论文 “ 计算机和智能 ” ,巧妙地把这个问题转化为一种可操作的方法,那就是测试。后来被称为图灵测试。简单说就是与其争论什么是“思维”,不如我们去做实验测试。通过了测试就叫计算机能思维,否则就说还达不到思维的水平。 图灵测试是这样设计的。测试分测试人员和被测试方两部分。被测试方由 A 和 B 构成, A 和 B 分别是一个人和一台被测试的计算机。测试人员和被测试方是分开的,提问和回答是通过一些中间设备实现的。测试人员并不知道 A 和 B 那个是人那个是计算机。测试时由测试人员分别向 A 和 B 提问,由被测试的人或者计算机回答问题。通过一系列的提问后,如果测试人员能够通过问题的回答,正确地分出 A 和 B 谁是人谁是机器,说明计算机还没有达到人的水平,那机器就没有通过图灵测试,如果测试人分不出 A 和 B 谁是机器谁是人,那这个机器就通过图灵测试。图灵指出: “ 如果机器在某些条件下,能够非常好地模仿人回答问题,以至提问者在相当长时间里误认它不是机器,那么机器就可以被认为是能够思维的。 ” 当时的计算机根本无法通过这一测试。图灵预言, 50 年内 , 即在 20 世纪末会有计算机通过图灵测试。图灵测试没有规定问题的范围和提问的标准,如果想要制造出能通过试验的机器,必须在电脑中储存人类所有可以想到的问题,储存对这些问题的所有合乎常理的回答,并且还需要理智地作出选择。这几乎是不可能的。到目前为止还没有电脑能通过图灵测试。但是如果限制在一定的领域和范围之内通过图灵测试是完全有可能的。 人工智能专家经过多年的努力,开发了不少智能软件,在理论和实践上取得了很大的进步。 1997 年 5 月 3-11 日, IBM 的计算机深蓝( Deep Blue )以 2 胜 1 负 3 平的成绩第一次战胜国际象棋冠军卡斯帕罗夫大师。在世界引起轰动。也可以说在一定意义下实现了图灵的预言。 自然对于图灵测试的理解以及它的作用等方面,学界也有各种不同的争论。而正是由于有这些争论才推动了科学技术的发展。 (未完待续)
那么,图灵机是啥样子的呢?它其实非常简单。图灵的主要构思之一,是考虑人在进行数学或者逻辑演算的时候是如何工作的。把人按照既定规则做计算和推理的这个操作过程加以最简化而得来的。具体而言,图灵机有下列零部件。 首先是一根一维的 带子 ,可以把它想象成一根纸带。带子分成确定的格子,每个格子里面可以写上记号,比如0和1,也可以为空,就是说没有写记号或者记号给抹掉了。这根带子是图灵机输入和输出的来源,也是图灵机记录中间结果的存储器。所以,这个带子的角色就好像一个人做算术或者逻辑推理时用的草稿纸那样。通常的草稿纸是二维平面的,比如除法演算的规则就告诉我们除数写在被除数左边,商写在被除数上面的横线之上,余数写在被除数相应位的底下,如此等等。但是按照图灵的分析,这种二维的安排,并不是必需的,因为只要有办法把哪个数写在哪里给有章有序地归置好,一维的带子就应该够用了。同时,也不需要太多种类的记号,因为更复杂的记号总可以由简单的给组合出来。比如,0、1和空白,就可以在二进制下做任何运算了。 人做计算时用纸,自然是为了看清纸上的数字,把下一步的结果用比较原子性的操作(比如一位数的加减乘除)一个个算出来,写到纸上,如此一步一步反复直到得到结果。所以就需要和草稿纸交互作用的机制,这在人就是用眼睛看,用手写。同样,图灵机的带子也有相应的读和写的机制。读在这里的意思,就是把带子上特定空格的 记号 给区分出来:0就是0,1就是1,空白就是空白;写的意思,就是在带子的特定空格放上个0或者1,替换掉了那里原来的记号,或者把那个格子抹成空白。我们平时做算术,在任何一个时刻,要么读和要么写,总是只在一个位置发生,比如读出被除数的某一位,或者写上商数的新的一位。即使我们有可能同时注视或者写出多位数,但这也可以分解成单独注视或者写出某一位。同样,在图灵机里,读和写在任何时间,只在一个空格进行。这样,我们就可以说有个 读写头 ,它就好像磁带录音机的磁头那样,在任何特定的时间总是在带子的一个特定的格子上方。要改变位置的话,就需要沿着带子挪动读写头,每次或左或右挪动一格。同样,如果需要挪多格的话,总可以通过反复挪动来实现。 有一点要说明的,就是图灵机的带子是没有头的,读写头向左或者向右都可以无穷无尽的走下去。更准确地讲,这个意思不是说在任何时候带子的长度是无限的,而是说在任何时候假使读写头往以便走到了带子在当前长度下的最后一格,那么总可以在头上再接上一段带子,让机器继续运行下去。这就好像草稿纸用完了,总可以再添一张。 有了带子(草稿纸)跟读写头(眼睛和铅笔或者说磁头),还缺负责计算的组织运作的东东。完成这个事情的,就是所谓控制器。这个可以想象成一个小盒子。盒子有特定的有限数目的状态。在不同的盒子状态下,机器可以有不同的行为,所以这个盒子才叫做控制器。具体状态在盒子里面是如何实现的不重要,比如可以用指针的位置或者用算盘珠子的位置,重要的是状态和状态之间可以分得一清二楚不会混淆。 艺术化的图灵机 [原图取自: Wikimedia Commons ] 有了这些基本零部件,我们就可以讨论如何让图灵机干活了。在任何一步上,决定图灵机做什么事情的有两方面的情况:(1)控制器现在的状态(这可以对应于现在的任务做到哪一步了(比如在做加法的话,可以是刚写了和,现在该写进位了),(2)读写头下面是什么;图灵机可以做三方面的事情:(3)从当前状态转移进入下一状态,与此同时(4)在当前格子上写个什么记号(包括用空白抹掉当前记号),并(5)让读写头在带子上左移一格、右移一格或是原地不动。所以,图灵机每一步做的事,就是根据它的(1)当前状态qi跟(2)当前读出的记号sj,决定(3)下一状态qij,(4)写出的记号sij,和(5)读写头的移动方向dij。 这样,图灵机的任何一步都可以用一个五元组来描述:( q i ,s j , q ij , s ij , d ij )。这里的下标 i 表示控制器的当前状态 q i 是所有可能状态之一,下标 j 表示当前读到的记号sj是所有的可能记号之一。两个合在一起的 ij 就表示新的状态 q ij ,写出的记号 s ij ,移动的方向 d ij 是由 q i 和 s j 共同决定的,或者说这三者分别都是 q i 和 s j 的函数。给定特定的一组( q i ,s j , q ij , s ij , d ij ),就是给定了图灵机在 q i 和 s j 下的行为,所以可以这样的五元组叫做图灵机的指令。当 q i 和 s j 不同的时候,就是说处于不同状态,读取不同记号的时候, q ij , s ij , d ij 相应地也可以取不同的(或者相同的)值,这样我们就有一些不同的五元组。把这些五元组都合到一起,就得到了决定了机器行为的 指令表 。我们通常想象指令表是存储在控制器里的,读写头是连在控制器上的。这样,在任何时刻,控制器就可以根据它的当前状态和带子上当前格子里的记号,决定图灵机的行为。 这里,有必要强调说明一下图灵机 彻底的离散性 。具体说来,带子是离散的:一格就是一格;记号是离散的:一个就是一个;控制器的状态是离散的:此状态非彼状态。读操作的区分和写操作的改变是离散的:读写头下面的是0,读到的就是0,写出的是1,格子上面出现的就是1,读的是啥、写的是啥不会有任何模糊之处。读写头移动是离散的:一格就是一格。状态转换是离散的:从状态甲到状态乙,没有中间状态可言,不会有混淆,不会有交叠。时间是离散的:读写操作、读写头移动、状态转化都是原子性的,一步完成,一步就是一步,没有完成了一半这样的说法。 举个具体的例子:二进制串奇偶性的检查。这里所谓的奇偶性是指二进制串里面有奇数个还是偶数个1。二进制串奇偶性这个概念挺有用。比如你和朋友之间发送消息,事先约定所有的消息都是7位,比如0101010,1110110,1111110,如此等等。这三个串里面,前两个有奇数个1,是奇串,后一个有偶数个1,是偶串。假设你们进一步约定,在发送消息前,每个7位的消息串尾巴上再增加一位,叫做校验位。这个校验位根据消息串的奇偶性来设置:如果消息串是奇,校验位就是1,否则就是0。这样,上面三个消息串在增加了奇偶校验位之后,就分别是01010101,11101101,11111100。然后你的朋友再把这样的包含校验位的8位的串,比如11101101,发送给你。如果传输正常,那么不管你的朋友发的是那个消息,这个8位的串都应该是偶串。这样,当你每收到一个串的时候,就可以对它进行 奇偶性检验 。如果你收到了一个偶串,比如11101101,那可能就没有问题(当然也可能有,比如,本来传输的是00101101,结果半路上前两位给反转而变成了11101101)。但是,如果你收到的是个奇串,比如10101101,那你就知道这中间肯定出问题了,至少有一位的0和1(一定有奇数个0和1)给反转过来了。于是,你就可以要求你的朋友重新传一次。通过这种奇偶校验,就可以抓住传输中发生的错误。 这个很有用的奇偶性检验,可以用图灵机来实现。把一个二进制串,放到带子上,串的两头的格子都是空白,读写头对准最左边的那一个非空白的数字(0或者1)。机器的任务是扫描并抹掉整个串,如果是个偶串,就在结束运行之前在带子上留下个0,如果是个奇串,就留下个1,而带子的其他格都是空白。 下面这个指令表,就能让图灵机实现奇偶性检验。在运行开始是,初始状态为偶。表中的H的意思是HALT,就是停机。遇到这个状态,机器就不再运行了。(所以,H不出现在 q i 那一列里面)。 ────────────────────────── ─── ─ ─── q i s j q ij s ij d ij ────────────────────────── ─── ── ─ ─ 偶 0 偶 空白 右 ────────────────────────── ─── ─ ─── 偶 1 奇 空白 右 ────────────────────────── ─── ─ ─ ── 偶 空白 H 0 - ─────────────────────────── ─── ─ ─ ─ 奇 0 奇 空白 右 ──────────────────────── ─── ───── ─ 奇 1 偶 空白 右 ─────────────── ── ─ ────────────── ─ 奇 空白 H 1 - ───────────────────── ─── ──────── ─ 下面看看为什么这个指令表能够完成任务。根据读写头当前所遇到的符号sj,首先,如果遇到0,就不改变状态:偶还是偶(第1行),奇还是奇(第4行);其次,如果遇到1,就改变状态,从偶到奇(第2行),从奇到偶(第5行);最后,如果遇到空白,读写头下面的不再是0或者1了,说明整个串都检查完了,这时,就可以根据状态输出0(第3行),或者输出1(第6行),并进入停机状态H。请注意,在整个过程中,除了进入停机状态H的时候,读写头不移动之外,读写头总是在向右移动;此外,除了进入H的那次,每读完一格,就把那格擦掉,所以 s ij 总是空白。 那么,我们通常所谓这个或者那个图灵机,就是指给定了一个如上表那样的指令表。给定了指令表之后,带子上的输入可以变,只要满足初始状态设置和读写头初始位置的条件,一个图灵机就应该可以对任何合法的输入串进行指令表所实现的处理。 跟学习编程序一样,学习理解图灵机如何运作的最好办法跟踪执行一些指令表和自己构造一些完成各种简单任务的指令表,比如做二进制加法、判断一个串是不是回文等等。 [声明:此处的图灵机,细节上不同于Turing于1936年提出的,属于现在比较通用的改进型。这里是基于明斯基的Computation: Finite and Infinite Machines。奇偶校验的例子,来自该书第120页。]
(1)图灵小时候说过的一句话: 我似乎总是想以最节能的方式,用自然界里最平常的东西来造各种东西。 I seem always to want to make things from the thing that is commonest in nature and with the least waste of energy. 见图灵妈妈Sara Turing的图灵传第23页。 (2)图灵被逮捕之后写下的三段论: 图灵相信机器会思维 图灵跟男人睡觉 所以机器不会思维 Turing believes machines think Turing lies with men Therefore machines do not think 出自:Andrew Hodges的Turing: Natural Philosopher (3)来自未现世界的消息之三 宇宙不过是大爆炸之光锥的内部。 The universe is the interior of the light cone of the Creation. 来自未现世界的消息是图灵自杀前三个月写给学生和朋友Robin Gandy的一组明信片的标题。详见Andrew Hodges的Alan Turing: The Enigma第513页。此处按照Hodges的解释把the Creation译作大爆炸。 (4)来自未现世界的消息之四 科学是微分方程。宗教是边界条件。 Science is a differential equation. Religion is a boundary condition. 这图灵对爱丁顿关于科学与宗教关系观点的概括。 (5)来自未现世界的消息之八 制定[泡利]不相容原理纯粹是为了电子们自己好, 如果让它们自由来往的话,它们恐怕会腐败堕落(而变成妖魔鬼怪)。 The Exclusion Principle is laid down purely for the benefit of the electrons themselves, who might be corrupted (and become dragons and demons) if allowed to associated too freely. 别忘了电子们是同性的,呵呵。