| 主页 | 频道首页 | 本站地图 | 论坛留言 | 合作联系 | 本站消息 | |
科技动态 技术发展 文化研究 生物生态 人的研究 生命起源 基因工程 科学普及 科学探索 专题其他

图灵-数学家

2012-04-01
著名数学家弗里曼·戴森的演讲:鸟和青蛙 图灵-数学家 个性化推荐猜你心 走近量子纠缠 图灵,数学家
图灵-数学家

邵伟文编

  阿兰?麦席森?图灵Alan Mathison Turing,1912年6月23日生于英国伦敦。是举世罕见的天才数学家和逻辑学家,被称为计算机科学之父、人工智能之父,是计算机逻辑的奠基者,提出了“图灵机”和“图灵测试”等重要概念。很可惜天才图灵却英年早逝,仅仅在世42年,然而他的影响在很多领域直到现在仍然能够感受到,人们为纪念其在计算机领域的卓越贡献而设立“图灵奖”。

  图灵的父亲J?M?图灵早年就读于牛津大学科帕斯克斯蒂学院历史系,后来从政,被派往印度担任民政部的官员.图灵的母亲E?S?斯托尼生于一个铁路工程师家庭,曾就读于巴黎大学文理学院,图灵是他们的次子。因为工作原因,孩子们经常住在一位朋友家中。图灵少年时就表现出独特的直觉创造能力和对数学的爱好。1926年,他考入伦敦有名的舍本公学,受到良好的中等教育.他在中学期间表现出对自然科学的极大兴趣和敏锐的数学头脑。

图灵天生悟性过人,16岁就能弄懂爱因斯坦的相对论,并且运用那深奥的理论独立推导力学定律。1927年末,图灵为了帮助母亲理解爱因斯坦的相对论,撰写了爱因斯坦的一部著作的内容提要,表现出他已具备非凡的数学水平和科学理解力。他对自然科学的兴趣使他在1930年和1931年两次获得自然科学奖,对自然科学的兴趣为他后来的一些研究奠定了基础,他的数学能力使他在念中学时就获得过国王爱德华六世数学金盾奖章。

1931年,图灵考入英国剑桥大学国王学院专攻数学,由于成绩优异而获得数学奖学金。在剑桥他的数学能力得到充分的发展。1935年,他的第一篇数学论文“左右殆周期性的等价”发表于《伦敦数学会杂志》,同年写出“论高斯误差函数”一文。这篇论文使得年仅23岁的图灵由一名大学生直接当选为国王学院的研究员,成为剑桥大学有史以来最年轻的研究员。次年图灵又因在概率论上的成就荣获英国著名的史密斯数学奖,成为国王学院声名显赫的毕业生之一。图灵在数学,尤其是数理逻辑学方面的深厚功底,令他几年后终于厚积薄发,一举成为计算机科学的创始人。

1936年5月,图灵写出了表述他的最重要的数学成果的论文“论可计算数及其在判定问题中的应用”,该文于1937年在伦敦权威的数学杂志《伦敦数学会文集》第42期上发表后,立即引起广泛的注意。这篇划时代的重要论文主要包括三方面的结果。

1、证明了Hilbert判定问题(Entscheidungsproblem)是没有答案的。Turing这一研究的起因是希望回答Hilbert计划中的可判定性问题。1928年,D. Hilbert正式提出了所谓的“Hilbert计划”,试图通过公理化方法建立数学的严格基础。特别是,Hilbert在其计划中提出了判定性问题,即是否存在一个算法“机械化”地判定每个数学分支中所有命题的正确性。1931年,奥地利数理逻辑学家哥德尔证明,即使是Peano算术这样简单的数学系统,也存在某些定理,尽管我们知道这些定理是对的,却不能够证明出来,从而给出了Hilbert判定性问题否定的回答。图灵认为,为了回答可判定性问题,首先需要明确可以用于判断的计算手段。他对哥德尔1931年在证明和计算的限制的结果作了重新论述,引进了“图灵机”概念,并证明图灵机的停机问题(halting problem)是不可判定的,这是说不可能用一个算法来决定一台指定的图灵机是否会在有限时间之内停机,通俗的说,停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决,则有一个程序判断其本身是否会停机并做出相反的行为,这时候不管停机问题的结果是什么都不会符合要求,事实上,假设存在一个程序P对停机问题可判定,即向程序P输入任意一个程序,要么在有限时间停机而输出“停机”,要么出现死循环而输出“死循环”,现在将此判定程序P作为数据输入该程序P本身,若该程序输入为“停机”,则有限时间该程序停机,从而成为“死循环”,矛盾!若该程序输入为“死循环”,则有限时间该程序出现死循环,从而“停机”,同样矛盾!所以这是一个不可判定的问题。从而给出了Hilbert可判定性问题的又一个反例。

2、引进了“图灵机”概念,给出了“可计算”的严格数学定义,开启了计算理论的研究。图灵机不是一种具体的机器,而是一种计算模型。根据丘奇-图灵假设,用任意算法可以计算的问题,都可以用图灵机计算。换句话说,图灵机为“计算”这个抽象术语提供了一个严格的数学模型,从而为可计算性理论奠定了基础。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,他把这样的过程看作下列两种简单的动作:

  在纸上写上或擦除某个符号;

  把注意力从纸的一个位置移动到另一个位置;

  而在每一个阶段,人如果要决定下一步的动作,依赖于(a)此人当前所关注的纸上某个位置的符号;(b)此人当前思维的状态。为了模拟人的这种运算过程,图灵构造出一台假想的机器,后来被数学家称为“图灵机”,该机器由以下几个部分组成:

  一、一条无限长的纸带。纸带被划分为一个接一个的小格子,每个格子上包含一个来自有限字母表的符号,字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依次被编号为0,1,2,……,纸带的右端可以无限伸展。

  二、一个读写头。该读写头可以在纸带上左右移动,它能读出当前所指的格子上的符号,并能改变当前格子上的符号。

  三、一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的,并且有一个特殊的状态,称为停机状态。

  四、一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作,并改变状态寄存器的值,令机器进入一个新的状态。

注意这个机器的每一部分都是有限的,但它有一个潜在的无限长的纸带,因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。

3、引入了可计算实数的概念。证明了可计算的实数是可数的,从而绝大部分实数是不可以计算的。对于某个实数,如果存在一个算法,它能给出该实数小数点后任意多位的数字,我们就把这个实数叫做“可计算数”。简单的说,可计算数就是那些能够编写程序打印出来的数。因此所有整数、有理数都是可计算数,所有代数数也都是可计算数,事实上很多超越数(比如 π 和 e )也都是可计算数。但是注意到,所有可能的程序代码的数量是可数的,因为我们能够按照代码长度从小到大把它们一一列举出来(代码长度相等时可以按字典序排序)。从而所有的可计算数也是可数的,它只占全体实数中很小的一部分。而绝大部分实数是不可以计算的。

1937年,图灵发表的另一篇文章“可计算性与λ可定义性”则拓广了丘奇(Church)提出的“丘奇论题”而形成“丘奇-图灵论题”,这个论题断言图灵机同直观的有效的函数计算具有等价的问题求解机制。即所有“能解”的问题都存在一个图灵机,只要把问题放在图灵机带子上,若有解则停机后带子内容即是解答。这个断言叫做“论题”是由于他无法严格证明。这个论题对计算理论的严格化,对计算机科学的形成和发展都具有奠基性的意义。1936年9月,图灵应邀到美国普林斯顿高级研究院学习,并与丘奇一同工作。他的研究涉及逻辑学、代数和数论等领域,成绩卓著。1938年在普林斯顿获博士学位,其博士论文题目为“以序数为基础的逻辑系统”,1939年正式发表,在数理逻辑研究中产生了深远的影响。

图灵参与解决的另一个著名的判定问题是“半群的字的问题”,它是图埃(Thue)在1914年提出来的:对任意给定的字母表和字典,是否存在一种算法能判定两个任意给定的字是否等价,给出有限个不同的称为字母的符号,便给出了字母表,字母的有限序列称为该字母表上的字。把有限个成对的字(A1,B1),…,(An,Bn)称为字典。如果两个字R和S使用有限次字典之后可以彼此变换,则称这两个字是等价的。1947年,波斯特(Post)和马尔科夫(Markov)用图灵的编码法证明了这一问题是不可判定的。1950年,图灵进一步证明,满足消元律的半群的字的问题也是不可判定的。

  1951年,年仅39岁的图灵被英国皇家学会选为会员,成为他们家族中的第四位皇家学会会员。从1952年直到去世,图灵一直在数理生物学方面从事非线性理论的研究。1952年发表了一篇论文“形态发生的化学基础”,他的兴趣主要是斐波那契叶序列,存在于植物结构的斐波那契数。他应用了反应-扩散公式,现在已经成为图案形成范畴的核心。图灵后期的论文都没有发表,一直到1992年《阿兰?图灵选集》出版,这些文章才得见天日。

图灵思想活跃,他的创造力也是多方面的。据他的同事们回忆,他在战时的秘密工作中,曾创造好几种新的统计技术,但都未形成论文发表,后来又重新为他人所创建,由A.瓦尔德(Wald)重新发现并提出的“序贯分析”就是其中之一。他对群论也有所研究,在“形态形成的化学基础”一文中,他用相当深奥而独特的数学方法,研究了决定生物的颜色或形态的化学物质(他称之为成形素)在形成平面形态(如奶牛体表的花斑)和立体形态(如放射形虫和叶序的分布方式)中的分布规律性,试图阐释“物理化学规律可以充分解释许多形态形成的事实”这一思想。直到80年代生物学界才开始探讨这一课题,图灵还进行了后来被称为“数学胚胎学”的奠基性研究工作,他还试图用数学方法研究人脑的构造问题,例如估算出一个具有给定数目的神经元的大脑中能存贮多少信息的问题等。这些至今仍然是吸引着众多科学家的新颖课题。人们认为,图灵是一位科学史上罕见的具有非凡洞察力的奇才,他的独创性成果使他生前就已名扬四海,而他深刻的预见使他死后倍受敬佩。当人们发现后人的一些独立研究成果似乎不过是在证明图灵思想超越时代的程度时,都为他的英年早逝感到由衷的惋惜。

原载:httpwww.ncmis.cas.cnkxcbjclyzs201203t20120314_89673.html



著名数学家弗里曼·戴森的演讲:鸟和青蛙
图灵-数学家
个性化推荐猜你心
走近量子纠缠
真实的投资银行世界
《心智、大脑与计算机——认知科学创立史导论》
脑瘫患者成为博士 已发表20余篇论文
“再牛逼的伟人,也有苦逼的青春”物理版
物理学步入禅境:缘起性空
世界著名咨询公司在华情况
马云在斯坦福大学的演讲
智猪博弈与激励机制设计与企业战略
饶毅的科学成就
屠呦呦和青蒿素
何祚庥:隻怨“谁叫你不幸生在了中国”
Nature上给做科研的四条黄金忠告
北京生命科学研究所所长王晓东谈饶毅落选院士
Foxit十年暗战反胜Adobe的故事
融合东西方智慧破解人类困境
为什么硅谷最牛的人在创业公司?
开曼谎言:中国企业的离岸秘史
Google早期的十个疯狂故事
罗斯柴尔德的中国生意
科学家与他们的上帝
被文明改变的人体
从社会网络角度看农民的生产协作,产品交换,社会资源配置
VIE会导致中国海外上市公司一文不值吗
谁对谁说了什么-Twitter研究进展
三大证据相继破灭:进化论,一个错误的信仰
霍金:天堂和来世只是害怕死亡者的童话故事
我们最该知道的10大科学定律及理论
给笔记本外接一个显示器的方法
世界著名实验室简介
伦理与政治考量过滤科学之真
人大讲座的开场白-大学生社会责任
浅析北美中国老板中的变态者 霍金和霍金辐射
李醒民专访:遨游在科学的三维世界里
人类学家提出可能引发地球崩溃的12个因素
无线WEP和WPA密码及破解原理
丘成桐:感情的培养是做大学问最重要的一部分
没有秘密——阿桑奇的理想
论抽象社会
科学与竞争:以日本物理学为例
《科学》主编:中国论文拒稿率高因投稿最多
“科学家一定需要博士帽吗”
如何培养自然科学领域的巨匠
爱因斯坦是如何获得诺贝尔奖的
美国多名退役军官曝UFO曾多次光顾该国核基地
哲学笔记I--被操纵的人性
PRL:物理定律可能并非全宇宙通用
李晓宁:形式逻辑为何产生于西方
《逻辑起源》连载
自然逻辑的产生、发展及意义
论现代逻辑
评论:被人为割裂的中国互联网
互联网大帝孙正义
城市交通网络拓扑结构复杂性研究
无线上网卡老掉线问题掉线的方法
科学家揭秘章鱼保罗预测的秘密
科学家和《阿凡达》里的科学
许成钢:经济学、经济学家与经济学教育
谢宇:漫谈定量与定性研究方法
如何在顶级科学杂志上发表论文
中国如何招聘教授:十年的变化和今后的趋势
学术资料账号密码全集汇总
混沌中的数学
幂律分布、幂律涌现与幂律谱
数学的若干发展和中国的数学
嘉路兰的螺旋历法理论
基金项目《动态评价网络的统计分析与信息挖掘》
人类文明的斐波那契演进
数学的常数美
科学创新犹如渔夫打鱼
超难的75道逻辑思维题
被禁70年的创富秘诀《硅谷禁书》
RSS文件形式
怀念路遥-贾平凹的BLOG
跨学科交流+开辟自己的领域=创新的境界
大师似苗如何栽
五大疯狂天才剖析
Windows 7下载及使用Windows 7升级
艺术与科学的“姻缘”——谈文艺复兴时期艺术与近代科学兴起的关系
Google TrustRank and Hilltop
实证研究方法
一位北大CCER研究生的经济学、金融学学习感悟
潘晓《人生的路啊怎么越走越窄》
Windows XP系统端口关闭方法
世界上最牛的论文
TXP1atform.exe中毒归来
google使用技巧
Widget发展和Widget的各种应用
身体语言密码29
现代科学研究专题其他1 现代科学研究专题其他2

本栏目主要介绍科学技术方面,包括现代科学研究成果、现代科技、现代科学技术、图灵-数学家等。特别关注有关人与文化的价值方面的研究。

『科学频道首页』 『本栏页首』 『关闭窗口』