图灵机的应用云计算课件

计算机模型与体系架构的发展

——

到云计算机一个非常简单的图灵机例子：

从左至右扫描一串二进制数字，如果该数字能够被3整除（是3的倍数）则在该数字串的末尾写出Y，否则写出N，然后停机。

—————————

|有限状态读写头|

—————————||\/———————————————|10101（无限长）存储带

———————————————

按照图灵（AlanTuring）给出的计算机模型，计算机是由一个有限状态读写头和一个存储器构成。有限状态读写头从一个初始状态开始，对存储器上的（输入）数据进行读或写操作，经过有限步操作之后停机，此时存储器上的（输出）数据就是计算结果。这样的计算机模型叫做图灵机。

存储带上的输入二进制字符串代表十进制数21，是3的倍数，的确读写头扫描完毕后会写出Y并停机。

图灵机模型对于一大类有限步数可计算问题给出了一个普适性的定义。每一个这样的问题都存在一个图灵机可对其进行计算给出答案。

我们知道对有些问题随机方法比确定的方法要快。随机计算方法的图灵机模型可以在基本图灵机上外加上一条存储带，存储着随机数串供有限状态读写头读取。·有限状态读写头——机器的程序执行代码·存储带处理——被处理的数据·Universal（通用）机器把有限状态指令存放在存储带上·让读写头根据读入的指令进行下一步操作

这样存储有指令的通用图灵机能够实现任何一个图灵机，比如我们在上面给出的专用图灵机，也就是说可以解决任意一个图灵可计算问题。

我们广泛使用的计算机的确就是采用了存储指令这一原理因而可以解决“万能”计算问题的。实现方法：待解决问题软件编制程序程序数据存放中央处理器指令数据操作

这样的机器也叫做“存储程序计算机”。在为第一台存储程序计算机EDVAC研发计划做顾问时，约翰·冯·诺伊曼写了一个草案报告描述了这种带有中央处理器、内存、I/O、总线的存储程序计算机。

所以存储程序计算机还有另外一个学名，叫做冯·诺伊曼体系架构（VonNeumannArchitecture）。图灵可计算：一个问题是否可以由一个图灵机在有限步数内完成。单个机器与两（多）台互相通信的机器要么都可以计算某个问题，要么都不可以。输入为一个二进制数字，输出为该数字的一进制编码计算时间与所需空间复杂度可以用输入中含有比特数目的指数函数来表示很低效的算法，但是它的确是一个图灵可计算问题。我们日常要计算的问题不光都是图灵可计算的，但是大量的问题是多项式步数内可以解决的问题。易解问题：即算法时间空间复杂度是输入比特数的一个多项式二进制转换为一进制问题具有指数复杂度，是难解问题易解问题都可以采用并行计算方法来加速求解（好的并行算法甚至可以达到线性（理想）加速，即使用p台处理器解决该问题的计算用时是使用1台处理器计算用时的1/p）快速排序（quicksort）快速排序（quicksort）是一个可以线性加速的问题“分而攻之”（divide-and-conquer）的方法来求解一个大问题可以分成p个彼此无关的小问题用p个处理器并行处理。现今很有名的（由于Google的推广工作）MapReduce函数编程方法是一个可以对任何大型可分解计算问题先做分解，将分解而得的许多小问题发出（Mapfunction）到许多分布机器上并行处理，然后对返回的非完整结果做组合（Reducefunction）得到完整结果的一个通用程序设计方法。用MapReduce方法可以对许多大型数据处理问题作有