html 网站 模板,怎样建立公司网页,高端+旅游+网站建设,网站建设价格套餐一.欢迎来到我的酒馆 第1章 1.7节#xff0c;图灵机的一个例子。 目录 一.欢迎来到我的酒馆二.图灵机2.1 艾伦-图灵简介2.2 图灵机简介 三.图灵机工作原理3.1 使用图灵机打印二进制数3.2 图灵机工作原理总结 四.总结 二.图灵机 本节内容主要介绍计算机科学之父——艾伦-图灵、…一.欢迎来到我的酒馆 第1章 1.7节图灵机的一个例子。 目录 一.欢迎来到我的酒馆二.图灵机2.1 艾伦-图灵简介2.2 图灵机简介 三.图灵机工作原理3.1 使用图灵机打印二进制数3.2 图灵机工作原理总结 四.总结 二.图灵机 本节内容主要介绍计算机科学之父——艾伦-图灵、以图灵名字命名的图灵机以及图灵机的工作原理。
2.1 艾伦-图灵简介 艾伦-麦席森-图灵Alan-Mathison-Turing1912年出生于英国伦敦。父亲朱利斯-麦席森-图灵Julius-Mathison-Turing是一名牛津大学的毕业生曾赴印度担任民政部官员。母亲埃塞尔-萨拉-斯托尼Ethel-Sara-Stoney毕业于巴黎大学文理学院曾任马德拉斯铁路的总工程师。父母都是受到良好教育的高材生说到这里这又会使人联系起我们之前介绍过的另外一位天才人物——莱布尼茨。他们两人的家庭环境颇为相似父母都是书香门第。耳濡目染受到父母亲的影响从小养成了热爱学习的习惯。可是图灵和莱布尼茨不同的是图灵在出生后不久便寄养在一个军人家庭由于工作的原因父母远赴海外印度工作很少时间回到英国在很大一部分时间里图灵和他哥哥都是由父母的朋友照顾。从小生活在寄养的家庭环境中这种成长环境对后来图灵的性格养成有着至关重要的影响。进入学校后图灵孤僻的性格让他很难和老师、同学相处。他无法与老师、同学亲近。在校园里也不受同学的欢迎同学们经常欺负图灵老师也不怎么喜欢他。然而图灵热爱研究数学他一直都沉浸在数学中。在小学时期图灵的学习成绩并不是很好因为这所小学偏重于哲学教育而图灵热爱自然科学在这里他并没有得到太多的关注老师还在他的成绩单上对他不重视语言的学习态度表示失望。 1926年图灵通过英国的普通入学考试进入舍本中学学习。刚进入中学的他学习成绩也不是很好即使是在他热爱的数学和物理也是如此。虽然学习成绩不好但是这并不能说明他在数学方面的天分他愿意花更多的时间来研究高等数学物理理论爱因斯坦的《相对论》而花在学校规定的课程上的时间少之又少。他花了大把的时间研究爱因斯坦的《相对论》以及物理理论上在年仅15岁的时候他就针对爱因斯坦的《相对论》写了一篇小论文送给母亲萨拉。即便在尖端学问上展现出了异于常人的天赋老师也没有过高的评价在他的期末评语上老师这样写到他花了太多时间研究高等数学而荒废了基础学科的学习。这时的他在老师眼里是一名孤僻的学生只研究自己喜欢的领域的怪孩子。然而这一切在他遇到一个男生之前开始有了变化。就在图灵写下小论文不久后图灵认识了比他大一个年纪的克里斯托弗-摩尔康Christopher-Morcom克里斯也是一个非常热爱自然科学的孩子。他们经常利用课余时间在一起学习高等数学和物理并培养出了浓厚的感情。图灵再后来和朋友的信中回忆说与克里斯相处的日子是非常快乐的。这段关系让图灵明白如何社交以及维持学业成绩。然而好景不长这段友谊并没有持续太久。1930年克里斯不幸得了感染病去世了。 1931年图灵以高分考入英国剑桥大学国王学院。在国王学院图灵开始了对高等数学的深入研究。由于学院的开放与包容身为研究鬼才以及同性恋的图灵在这里得到了前所未有的包容他终于可以研究自己喜欢的事情了。在国王学院图灵修了许多高等数学和物理相关课程这为他后来在自然学科做出突出贡献打下了基础。1935年图灵在一篇论文里面假想了一台自动化机器简称为A机器这台机器的概念中包含了四个元素一条无限长纸带纸带被划分成一个个小个子每个小格子里面写有数字0或1一个可以读取纸带方格的读写头一套预先制定好的指令这套指令可以规定机器如何运作一个可以暂时存储机器状态的记忆体。由这四个部分组成的机器就是大名鼎鼎的图灵机。这套机器的读写头可以在纸带的小方格上自由移动并且可以改变每个小方格内包含的数据信息而预先设计好的规则会指定机器在当前状态下应该做什么倘若这套规则中不存在针对当前状态的指令机器就会停止运作。这套机器也成为后来电脑的原型我们称这套机器最早的版本为图灵机图灵机的概念具有开创性而在图灵机刚被设计出来的时候并没有得到重视直到二战爆发图灵机才显示出了它的威力。 电影《The Imitation Game模仿游戏》就是以二战为背景讲述了纳粹德国使用恩尼格玛Enigma加密文件恩尼格玛的存在使得英国与德国在大西洋海战中节节败退英国想方设法地破解纳粹德国的加密文件而用恩尼格玛加密的文件有一亿亿种可能性如果依靠人力去破解需要2000万年的时间。英国军方招揽了大量的密码学人才图灵自然也在其中图灵破译加密文件的思想是使用机器来打败机器。纳粹德国使用恩尼格玛密码机加密了文件那我们就可以设计一套机器来解密按照这个思想图灵设计了一套机器可以即时破解加密文件。虽然在现在来说图灵设计的这套机器连电脑都算不上顶多是一个机械式计算器但是它的存在扭转了战局使得德军的加密文件无处遁形。图灵和他的团队无疑是结束第二次世界战争的大功臣更有专家表示若是没有图灵等人的破译二战还会再持续至少两年。战事结束之后图灵被英国政府授予了第四级的大英帝国勋章。 这样一位大功臣照理说会受到人们众星捧月般的爱戴然而图灵在战后的生活可谓是一个悲剧。1953年图灵家中被盗。在不久之后图灵就报警了希望警察可以快速处理此案。然而在做笔录的时候当被问道图灵和他同伴的关系时图灵直接承认了自己是同性恋这件事情非同小可因为在那时的法律里规定同性恋也是一种犯罪行为。偷窃案不了了之图灵反而身陷同性恋的案子中法院给出了两种选择一种是注射雌性激素另一种是坐牢。图灵选择了前者注射雌性激素会产生荷尔蒙并且对身体有很大的副作用。过量的荷尔蒙对图灵的身体造成很大的影响他不再像从前那样可以长跑、骑车了。图灵还因为这件事情失去了政府顾问的资格并且规定永远不能入境美国。1954年在被定罪两年后图灵在公寓里服了含有氰化钾的苹果去世享年41岁。 1966年美国计算机协会ACM设立图灵奖奖励那些在计算机科学领域做出突出贡献的人图灵奖是计算机科学领域的最高奖项被誉为计算机界的诺贝尔奖。 2009年英国政府就图灵受到的迫害一事公开道歉。2013年英国女王向图灵追加了皇家赦免令赦免令说图灵在战争期间的解密工作以及在计算机科学方面的研究应该得到铭记和认可。
2.2 图灵机简介 图灵机Turing Machine简称 “TM”是一种抽象的计算模型。1936年图灵发表了一篇论文《论可计算的数及其在密码问题中的应用》首次提出了逻辑机的通用模型图灵将这种机器称为 “A机器“或 “自动机器”后来人们把这个通用模型命名为图灵机。图灵机是一种可计算的数学模型它可以简化问题。这种模型可以将人们使用纸和笔进行数学运算的过程进行抽象由一个不存在的机器代替人们手动数学运算。这种理念使得人们可以借助机器来计算各种数学运算大大节省了时间。并且图灵提出的 ”A机器“ 或 ”自动机器“ 在后来启发了冯-诺依曼设计出了可存储程序计算机我们今天使用的计算机使用的正是冯-诺依曼设计的计算机架构。 图灵机由四个部分组成一条无限长的纸带一个可以读取纸带的读写头一个可以存储读写头状态的记忆体一套预先设计好的指令。这条纸带被平均分割成一个个小格子小格子里可以写入数据比如0和1读写头可以在纸带上左右移动移动方向有三个RLN分别是右移左移不移动每次只能移动一个格子读写头上有一个记忆体可以存储当前读写头的状态State比如用q0表示起始状态。读写头一次不仅可以读取一个小方格内的数据也可以向一个小方格内写入数据也可以擦除小方格内的数据也就是小方格内什么也没有。至于是读取纸带中的数据还是向纸带中写入数据完全由一套预先设计好的指令决定。读写头的操作流程全部依靠预先设计好的指令执行一条指令包括五个部分起始状态字母表读取或写入的数据读写头移动方向下一个状态。
三.图灵机工作原理 前面详细地介绍了图灵机的组成在我们了解了图灵机的大致原理之后我们继续探讨图灵机的工作原理。
3.1 使用图灵机打印二进制数 简而言之图灵机由以下四个部分组成一条无限长的纸带一个读写头一个保存读写头状态的记忆体一套预先设计好的指令。下面我们用图灵机模型打印出二进制数111通过这种方式介绍图灵机的工作原理。在开始之前我们需要制定一套指令读写头根据我们预先设计好的指令运行。因此我们规定读写头的起始状态为q0终止状态为q3状态集为{q0q1q2q3}字母表为{01BB表示Blank}行动集为{LRNN表示不移动}。我们的需求是使用图灵机模型在纸带上打印出二进制数111根据这个需求可以写出一套指令
{q0,B,1,R,q1}
{q1,B,1,R,q2}
{q2,B,1,N,q3}有了指令图灵机就可以根据这套指令来执行下面我们演示在纸带上打印出二进制数111的步骤 首先根据第一条指令{q0,B,1,R,q1}把读写头的当前状态记录为q0这是读写头的起始状态接着是B这是字母表表示当前小方格内什么数据也没有。这时候我们读取了两个数据q0和B这是指令的前两个数据我们可以把指令{q0,B,1,R,q1}拆分成一个规则集规则集通俗来讲就是方便我们查看指令用的按照上面的三个指令我们可以写出对应的规则集 第二写好了指令图灵机就可以根据指令运行。按照我们之前定义的需求在一条空白的纸带上打印出二进制数111。图灵机会逐条地执行指令第一条执行的指令是{q0,B,1,R,q1}q0表示读写头的当前状态B表示当前纸带上的小方格为空白什么数据也没有。第一条指令的前两位数据是q0和B根据这个我们可以去规则集表里查询到第一条指令的操作后面的三位数据就是具体的操作{q0,B,1,R,q1}1表示读写头写入的数据R表示在写入数据完成后读写头需要往右移动一格q1表示更新读写头的内部状态由最初的q0更新为q1。 下图演示了图灵机在执行指令{q0,B,1,R,q1} 的操作流程 接着执行指令{q1,B,1,R,q2} 执行最后一条指令{q2,B,1,N,q3} 三条指令全部执行完成后在纸带上就输出了一个二进制数111。
3.2 图灵机工作原理总结 图灵机是一种抽象的计算模型它可以将人们使用纸和笔计算数学运算进行抽象使用机器来代替人们手动数学运算。这种理念使得人们可以借助机器来进行各种数学运算极大的缩减了人们用于数学运算上的时间。后来的冯-诺依曼结构正是受到了图灵机的启发设计出了可存储程序计算机这正是现在计算机的原型。图灵机按照预先设计好的指令来运行一条指令包括五个部分读写头的起始状态小方格内当前的数据需要写入的数据读写头的移动方向读写头下一个状态。 状态集{q0q1q2q3qn}q0为读写头的起始内部状态终止状态可以手动确定 字母表{01B}B表示Blank空白 行动集{LRN}N表示不移动
四.总结
1.介绍艾伦-图灵的个人生平。图灵设计的机器是破译 “恩尼格玛” 的关键。 2.介绍图灵机。图灵机是一种抽象的计算模型它可以代替人们手动进行数学运算极大的缩减了在数学运算上的时间。 3.介绍图灵机的工作原理。图灵机是按照预先设计好的指令执行一条指令明确指定了读写头的内部状态写入纸带小方格的数据以及更新读写头的内部状态。 4.参考资料 (1) 艾伦-图灵简介https://baike.baidu.com/item/%E8%89%BE%E4%BC%A6%C2%B7%E9%BA%A6%E5%B8%AD%E6%A3%AE%C2%B7%E5%9B%BE%E7%81%B5/3940576?frge_ala (2) 图灵机简介https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html
