实验一 图灵机模型与计算机硬件系统虚拟拆装

五、实验报告

实验名称：

学号  姓名                班级：       实验时间：     年  月  日 

实验报告表1-1图灵机模型中的主要组成部分及作用

说明：可根据需要加行

实验报表1-2冯.诺依曼计算机体系结构的功能描述

实验报告表1-3 实验所使用的计算机硬件配置登记表

实验报告表1-4 微型计算机拆卸顺序记录表

实验报告表1-5 微型计算机安装顺序记录表

实验报告表1-6 微型计算机安装顺序调整记录表

说明：可根据需要加行

实验报告表1-7  6个指定部件的安装顺序记录表

实验报告表1-8 扩充内存

实验报告表1-9更换显卡

第二篇：图灵机(数学模拟计算机)之数学原理(加精)

图灵机（数学模拟计算机）之数学原理（加精）_大学数学吧_百度贴吧图灵机（数学模拟计算机）之数学原理（加精）注册|登录新闻 网页 贴吧 知道 MP3 图片 视频 百科 吧内搜索 | 帮助进入贴吧 进入i贴吧 贴子搜索百度贴吧 > 大学数学吧 > 浏览贴子 吧主： 快速回复 贴吧投诉 国电亚光 交流可调稳压电..国电亚光提供交流可调稳压电源,亚光是国内历次电源革命的先行者,..上虞华成风机优价供应风机..本公司专业生产各种风机,风机箱等系列通风设备,并对外提供各种风..河北彩钢 具有良好的隔热,..张家口乾源彩钢有限责任公司生产的产品具有安装迅速的特点,与采..工程宝供应,首选:北京普洋..数字化工程宝是工程商对设备安装,调试及维护的必备设备.它集监视..专业显示器专业供应商能人电脑中国总代理NEC专业显示器 ISP高端面板,多功能用途专业显..液位变送器 宇航专业生产宇航专业生产销售液位变送器 领先业界 产品深受新老客户满意 值...cn销售代理国内外名牌电气产..专营韩国工控自动化电气产品 韩国LS LG电气产品一级代理商代理销售日本OKI芯片OKI芯..上海东靖数码电子科技代理销售OKI芯片 技术精湛,服务真诚电话021...cn大连宝星ups电源首选大连..大连宏力德专业大连宝星ups电源销售国际,国内知名品牌UPS电源,EP..国际领先 科力奥传感器设..中国卫星与英国胜思特合作的技术结晶 国内供应高精度压力传感器...cn转贴次数：0共有8篇贴子 1图灵机（数学模拟计算机）之数学原理（加精）普适图灵机的概念。虽然其细节是复杂的，但是它背后的原则并不十分复杂。它的基本思想是把任意一台图灵机T的指令的表编码成在磁带上表示成0和1的串。然后这段磁带被当作某一台特殊的被称作普适图灵机U的输入的开始部分，接着这台机器正如T所要进行的那样，作用于输入的余下部分。普适图灵机是万有的模仿者。“磁带”的开始部分赋予该普适机器U需要用以准确模拟任何给定机器T的全部信息！ 为了了解这是如何进行的，我们首先需要一种给图灵机编号的系统方式。考虑定义某个特殊的，譬如讲在前面描述的图灵机的一个指令表。我们必须按照某种准确的方案把这表编码成0和1的串。我们可借助于以前采

用的“收缩”步骤来办到。因为，如果我们用数2，3，4，5和6来分别代表符号R、L、STOP、箭头（→）以及逗点，那么我们就可以用１１０、１１１０、１１１１０、１１１１１０以及１１１１１１０的收缩把它们编码。这样，出现在该表中的这些符号实际的串可以采用分别被编码成０和１０的位数0和１。由于在该图灵机的表中，在二进位计数的结尾大写的数的位置足以把大写的０和１从其他小写的阿拉伯数字中区分开来，所以我们不需要用不同的记号。这样，110１将被读成二进位数1101，而在磁带上被编码成１０１００１０。特别是，0０读作00，它可毫不含糊地被编码成０，或者作为被完全省略的符号。实际上我们可以不必对任何箭头或任何在它紧前头的符号进行编码，而依靠指令的数字顺序去标明哪些符号必须是什么。尽管在采用这个步骤时，在必要之处要提供一些额外的“哑”指令，以保证在这个顺序中没有缝隙。这样的做法具有相当好的经济性。（例如，图灵机XN+1没有告诉我们对110０要做什么的命令，这是因为这条指令在机器运行时从不发生，所以我们应该插入一条“哑”指令，譬如讲110０→0０R，它可合并到表中而不改变任何东西。类似地，我们应该把10１→0０R插入到XN×2中去。）若没有这些“哑的”，表中后面的指令的编码就会被糟蹋了。因为在结尾处的符号L或R足以把一条指令和另一条隔开，所以我们在每一指令中实际不需要逗号。因此，我们采用下面的编码： ０表示0或０，１０表示1或１，１１０表示R，１１１０表示L，１１１１０表示stop。 作为一个例子，让我们为图灵机XN+1编码（插入指令110０→0０R）。在去掉箭头和在它们紧前面的位数以及逗号之后，我们得到 0０R 1１R 0０R 10１R 11０L 10１R 0１STOP 100０L 101１L 100１L110０R10１R0０R111１R 11１R 111０R 为了和早先说的相一致，我们可以去掉每一个００，并把每一个01简单地用1来取代，这样得到 R1１RR10１R11０L10１R１STOP100０L101１L1 00１L110０R10１RR111１R11１R111０R 如下是在磁带上的相应的码： １１０１０１０１１０１１０１００１０１１０１０１００１１１０１００１０１１０１０１１１１０１００００１１１０１００１０１０１１１０１０００１０１１１０１０１０００１１０１００１０１１０１１０１０１０１０１０１１０１０１０１０１１０１０１０１００１１０ 我们总是可以把开始的１１０（以及它之前的无限的空白磁带）删去。由于它表示0０R，这代表开头的指令0０→0０R。而

我已隐含地把它当作所有图灵机共有的。这样仪器可从磁带记号左边任意远的地方向右跑到第一个记号为止。而且，由于所有图灵机都应该把它们的描述用最后的１１０结束（因为它们所有都用R、L或STOP来结束），所以我们也可把它（以及假想跟在后面的０的无限序列）删去。这可以算作两个小节约。所得到的二进位数是该图灵机的号码，它在XN+1的情况下为： １０１０１１０１１０１００１０１１０１０１００１１１０１００１０１１０１０１１１１０１００００１１１０１００１０１０１１１０１０００１０１１１０１０１０００１１０１００１０１１０１１０１０１０１０１０１１０１０１０１１０１０１０１００。 作者：人工智能博士 0位粉丝 2006-7-20 17:16 回复此发言 2图灵机（数学模拟计算机）之数学原理（加精）这一特殊的数在标准十进位记号下为 450813704461563958982113775643437908。 我们有时不严格地把号码为n的图灵机称为第n台图灵机，并用Tn来表示。这样，XN+1是第450813704461563958982113775643437908台图灵机！ 我们必须顺着这图灵机的“表”走这么远，才找到一台甚至只进行如此平凡的（在扩展二进位记号上）对自然数加一的运算，这真使人印象深刻！（尽管在我的编码中还可以有很少的改善余地，但我认为自己进行得相当有效率。）实际存在某些更低号码的有趣的图灵机。例如，UN+1的二进位号码为 １０１０１１０１０１１１１０１０１０ 它只是十进位制的177642！这样，只不过是把一个附加的1加到序列1的尾巴上的特别平凡的图灵机UN+1是第177642台图灵机。为了好奇的原因，我们可以注意在任一种进位制中“乘二”是在图灵机表中这两个号码之间的某处。我们找到XN×2的号码为10389728107，而UN×2的号码为149xxxxxxxxxxxx026917547669。 人们从这些号码的大小，也许会毫不奇怪地发现，绝大多数的自然数根本不是可工作的图灵机的号码。现在我们根据这种编号把最先的十三台图灵机列出来： T0：0０→0０R，0１→0０R， T1：0０→0０R，0１→0０L， T2：0０→0０R，0１→0１R， T3：0０→0０R，0１→0０STOP， T4：0０→0０R，0１→1０R， T5：0０→0０R，0１→0１L， T6：0０→0０R，0１→0０R，1０→0０R， T7：0０→0０R，0１→？？？， T8：0０→0０R，0１→10０R， T9：0０→0０R，0１→1０L， T10：0０→0０R，0１→1１R， T11：0０→0０R，0１→0１STOP， T12：0０→0０R，0１→0０R

，1０→0０R。 其中，T0简单地就是向右移动并且抹去它所遇到的每一件东西，永不停止并永不往回退。机器T1最终得到同样的效应。但它是以更笨拙的方法，在它抹去磁带上的每个记号后再往后跳回。机器T2也和机器T0一样无限地向右移动，但是它更有礼貌，简单地让磁带上的每一件东西原封不动。由于它们中没有一台会停下，所以没有一台可以合格地被称为图灵机。T3是第一台可敬的机器。它的确是在改变第一个（最左边）的１为０后便谦虚地停止。 T4遭遇了严重的问题。它在磁带上找到第一个１后就进入了一个没有列表的内态，所以它没有下一步要做什么的指令。T8、T9和T10遇到同样的问题。T7的困难甚至更基本。把它编码的０和１的串涉及到五个接续的１的序列：１１０１１１１１０。对于这种序列不存在任何解释，所以只要它在磁带上发现第一个1就被绊住。（我把T7或其他任何机器Tn，它的n的二进位展开包含多于四个１的序列称为不是正确指明的。）机器T5、T6和T12遭遇到和T0、T1和T2类似的问题。它们简单地、无限地、永远不停地跑下去。所有T0、T1、T2、T4、T5、T6、T7、78、T9、T10和T12都是伪品！只有T3和T11是可工作的，但不是非常有趣的图灵机。T11甚至比T3更谦虚，它在第一次遇到1时就停止，并且没有改变任何东西！ 我们应该注意到，在表中还有一个多余。由于T6和T12从未进入内态1，机器T12和T6等同，并在行为上和T0等同。我们既不必为这个多余，也不必为表中的图灵机伪品而烦恼。人们的确可以改善编码以摆脱许多伪品和大大减少重复。所有这些都是以使我们可怜的普适图灵机变得更复杂作为代价。普适图灵机必须把所读到的号码n解码并假装成图灵机Tn。如果我们可以把所有伪品（或者多余量）取走，这还是值得做的。但是，我们很快就会看到，这是不可能的！这样，我们就不触动我们的编码好了。 例如，可方便地把具有 …０００１１０１１１００１００００… 接续记号的磁带解释成某个数字的二进位表示。我们记得０在两端会无限地继续下去，但是只有有限个１。我还假定１的数目为非零（也就是说至少有一个１）。我们可以选择去读在第一个和最后一个1（包括在内）之中的有限的符号串，在上述的情况是为一自然数的二进位写法 作者：人工智能博士 0位粉丝 2006-7-20 17:16 回复此发言 3图灵机（数学模拟计算机）之数学原理（加精）１１０１１１００１， 它在十进位表示中为441。然而，这一过程只能给我们奇数（其二进位表示以１结尾的

数）。而我们要能表示所有的自然数。这样，我们采取移走最后的１的简单方案（这个１仅仅被当作表示这一程序的终止记号），而把余下来的当成二进位数来读5。因此，对于上述的例子，我们有二进位数 １１０１１１００， 它是十进位的220。这个步骤具有零也用磁带上的记号代表的好处，也就是 …００００００１００００００… 我们考虑图灵机Tn对我们从右边提供给它的磁带上（有限的）０和１的串的作用。根据上面给出的方案，可方便地把这串也考虑作某一个数，譬如m的二进位代表。我们假定，机器Tn在进行了一系列的步骤后最终到达停止（即到达STOP）。现在机器在左边产生的二进位数串是该计算的答案。让我们也以同样方式把这当作，譬如是p的二进位代表来读。我们把表达当第n台图灵机作用到m上时产生p的关系写成： Tn(m)=p。 现在，以稍微不同的方式看这一关系。我们把它认为是一种应用于一对数n和m以得到数p的一个特别运算。（这样，若给定两个数n和m，视第n台图灵机对m作用的结果而得出p。）这一特别运算是一个完全算法的步骤。所以它可由一台特殊的图灵机U来执行。也就是说，U作用到一对(n，m)上产生p。由于机器U必须作用于n和m两者以产生单独结果p，我们需要某种把一对(n，m)编码到一条磁带上的方法。为此，我们可假定n以通常二进位记号写出并紧接着以序列１１１１１０终结。（我们记得，任一台正确指明的图灵机的二进位数都是仅仅由０，１０，１１０，１１１０和１１１１０组成的序列，因此它不包含比四个１更多的序列。这样，如果Tn是正确指明的机器，则１１１１１０的发生的确表明数n的描述已终结。）按照我们上面的规定，跟着它的每一件东西简单地是代表m的磁带（也就是，紧跟二进位数m的是１０００…）。这样，这第二个部分简单地就是Tn假设要作用的磁带。 作为一个例子，如果我们取n=11和m=6当作U要作用的磁带，其记号序列为 …０００１０１１１１１１１０１１０１００００… 这是由以下组成的： …００００（开始的空白带） １０１１（11的二进位表示） １１１１１０（终结n） １１０…（6的二进位表示） １００００…（余下的磁带）。 在Tn作用到m上的运算的每一接续的步骤，图灵机U要做的是去考察n的表达式中的接续数位的结构，以使得在m的数位（也就是Tn的磁带）上可进行适当的代换。在原则上（虽然在实践中肯定很繁琐）不难看到人们实际如何建造这样的一台机器。

它本身的指令表会简单地提供一种，在每一阶段读到被编码到数n中的“表”中，应用到m给出的磁带的位数时，合适元素的手段。肯定在m和n的数位之间要有许多前前后后的进退，其过程会极为缓慢。尽管如此，一定能提供出这台机器的指令表，而我们把它称为普适图灵机。把该机器对一对数n和m的作用表为U(n,m)，我们得到： U(n,m)=Tn(m)。 这儿Tn是一台正确指明的图灵机6。当首先为U提供数n时，它准确地摸拟第n台图灵机！ 因为U为一台图灵机，它自身也必须有一号码；也就是说，我们有 U=Tu 此处号码u待定。u究竟是多少呢？事实上我们可以准确地给出u=72448553353393175771983950xxxxxxxxxxxx236067255xxxxxxxxxxxx7966065xxxxxxxxxxxx031048361363235936564444345838222688327876762655614469281411771501784255170755408565768975334635694247848859704693472573998858228382779529xxxxxxxxxxxx16983594593879188554xxxxxxxxxxxx50582055598xxxxxxxxxxxx414896033xxxxxxxxxxxx5362503498452983232065158304766xxxxxxxxxxxx329717234151056980262734686429921838172157333482823073453713421475059740345184372xxxxxxxxxxxx24321077342178851492760797597xxxxxxxxxxxx8639635449226915947965461471134570014504816733756217257346452273105448298078496512698878896xxxxxxxxxxxx2044779890219144379328300194935709639217039048332708825962013017737272027186259199144282754374223513556751340842222998893744105343054710443686xxxxxxxxxxxx8019437530813870639942772823156425289237514565xxxxxxxxxxxx93241144826142357286193118332xxxxxxxxxxxx318xxxxxxxxxxxx7633xxxxxxxxxxxx75045635852164214869542347187426437544xxxxxxxxxxxx270912404220765387542644541334517485662915742999095026230097337381377241621727xxxxxxxxxxxx6854002893566085696822620141982486216xxxxxxxxxxxx029857060017430067008689675903447341741278xxxxxxxxxxxx36639389969058177385916540xxxxxxxxxxxx133222163141xxxxxxxxxxxx786695997045096xxxxxxxxxxxx3656015145xxxxxxxxxxxx4800348224xxxxxxxxxxxx188429899393135266882xxxxxxxxxxxx6191070146196852319284748203449589770xxxxxxxxxxxx58174873332729667899879847328409819076485xxxxxxxxxxxx166787363477605857245036964434897992034489997455662402937487668839751404451665xxxxxxxxxxxx83991xxxxxxxxxxxx44xxxxxxxxxxxx623923792115253181625xxxxxxxxxxxx286xxxxxxxxxxxx13xxxxxxxxxxxx51833519956891397481375049xxxxxxxxxxxx3651980186945639498 作者：人工智能博士 0位粉丝 2006-7-20 17:16 回复此发言 4回复：图灵机（数学模拟计算机）之数学原理（加精）yiu xi 作者：风儿武 0位粉丝 2006-7-20 22:23 回复此发言 5回复：图灵机（数学模拟计算机）之数学原理（加精）帅气！顶一个 作者：jackbore 0位粉丝 2008-10-14 22:34 回复此发言 6回复：图灵机（数学模拟计算机）之数学原理（加精）问一个简单的小问

题，让电脑（对话同人），作诗更难我只答案--下岗人 作者：nym2 0位粉丝 2008-11-1 10:08 回复此发言 7回复：图灵机（数学模拟计算机）之数学原理（加精）问一个简单的小问题，让电脑（对话同人），比作诗 图灵的退化问题 作者：nym2 0位粉丝 2008-11-1 10:10 回复此发言 8回复：图灵机（数学模拟计算机）之数学原理（加精）...... 找搬皇帝新脑 作者：58.253.125.* 2009-1-18 16:52 回复此发言 共有8篇贴子 发表回复标　题: 内　容: 图片/视频链接: (如何贴图/贴视频？)用户名:您目前是匿名发表 登录 | 注册验证码: 请点击后输入验证码，加入会员后本吧发贴免验证码。 ©2010 Baidu 贴吧协议 意见反馈