图灵机的应用(云计算).ppt
《图灵机的应用(云计算).ppt》由会员分享,可在线阅读,更多相关《图灵机的应用(云计算).ppt(13页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、计算机模型与体系架构的发展 从图灵机 到云计算机一个非常简单的图灵机例子:从左至右扫描一串二进制数字,如果该数字能够被3整除(是3的倍数)则在该数字串的末尾写出Y,否则写出N,然后停机。|有限状态读写头|/|10101 (无限长)存储带 按照图灵(Alan Turing)给出的计算机模型,计算机是由一个有限状态读写头和一个存储器构成。有限状态读写头从一个初始状态开始,对存储器上的(输入)数据进行读或写操作,经过有限步操作之后停机,此时存储器上的(输出)数据就是计算结果。这样的计算机模型叫做图灵机。这个读写头共有3个状态:“状态一”为初始状态,按如下方法从左至右扫描存储带上的数字或写出字符:|有
2、限状态读写头|/|10101 (无限长)存储带 状态一:读入为0,留在状态一,读入为1,进入状态二,读入为空,写Y,停机。状态二:读入为0,进入状态三,读入为1,进入状态一,读入为空,写N,停机。状态三:读入为0,进入状态二,读入为1,留在状态三,读入为空,写N,停机。存储带上的输入二进制字符串代表十进制数21,是3的倍数,的确读写头扫描完毕后会写出Y并停机。图灵机模型对于一大类有限步数可计算问题给出了一个普适性的定义。每一个这样的问题都存在一个图灵机可对其进行计算给出答案。我们知道对有些问题随机方法比确定的方法要快。随机计算方法的图灵机模型可以在基本图灵机上外加上一条存储带,存储着随机数串供
3、有限状态读写头读取。有限状态读写头机器的程序执行代码 存储带处理被处理的数据 Universal(通用)机器把有限状态指令存放在存储带上 让读写头根据读入的指令进行下一步操作 这样存储有指令的通用图灵机能够实现任何一个图灵机,比如我们在上面给出的专用图灵机,也就是说可以解决任意一个图灵可计算问题。我们广泛使用的计算机的确就是采用了存储指令这一原理因而可以解决“万能”计算问题的。实现方法:待解决问题软件编制程序程序数据存放中央处理器指令数据操作 这样的机器也叫做“存储程序计算机”。在为第一台存储程序计算机EDVAC研发计划做顾问时,约翰冯诺伊曼写了一个草案报告描述了这种带有中央处理器、内存、I/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图灵机 应用 计算
限制150内