最早认识到“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