而且将其作为运算的一部分银河国际手机app

当前位置:银河国际app下载 > 银河国际手机app > 而且将其作为运算的一部分银河国际手机app
作者: 银河国际app下载|来源: http://www.jtxdm.com|栏目:银河国际手机app

文章关键词:银河国际app下载,图灵机

  求两数的最大公约数,如求3654和1365的最大公约数(辗转相除法,图左):

  算法代表着用系统的方法描述了解决问题的步骤,即能够对一定规范的输入,在有限时间内获得所要求的输出。银河国际手机app而一般算法概念的准确表达最直接、最有说服力的、也是历史上最重要的当然是图灵机了。

  为了解决成为可判定性问题的一个范围广泛的问题。图灵设想如何才能把“机器”的概念表达出来,银河国际手机app它的动作被分解成基本的步骤。这样,由人类数学家在解决数学问题时进行的任何活动,都可以被冠以“机械步骤”之名。

  图灵设想实现某种(可以有限地定义的)计算步骤的一台机器。我们要求这台仪器具有有限数目的不同可能态的分立集合。我们称之为仪器的内态。在欧几里得算法求最大公约数时,无论这些数有多大,计算步骤都是有限的,即该算法是指令的同一有限集合。虽然仪器只有有限个内态,它却能处理大小不受限制的输入。

  由于该仪器只有有限数目的不同的内态,不能指望它把所有外部数据和所有自己计算的结果“内化”(相当于我们用java运行一段程序,控制台输出的时候只显示最终的结果,而计算过程所产生的所有中间结果都被内化,只产生最终结果)。也许可在外存空间把那个运算的相关结果记下来,然后以一种精确决定的方式进行下一个阶段的运算。

  (输入和输出的环境就是理想化的粗纸或者磁带;内部称为硬件,外部称为软件)

  图灵是按照在上面做记号的“磁带”来描述其外部数据和存储空间的。一旦需要,仪器就会把该磁带调来“阅读”,而且将其作为运算的一部分,磁带可前后移动。仪器可把记号放到需要的地方,可抹去旧的记号,允许同一磁带像外存(也就是“粗纸”)以及输入那些动作。 因为有时一个计算的中间结果可作为新的数据继续进行运算,故“外存”和“输入”的概念不必分开,在欧几里得算法中,不断地用计算不同阶段的结果去取代原先的输入(数A和B)。

  图灵机的绝妙之处就是将一般算法的抽象问题数字逻辑化,用二进制的概念将计算问题机械的步骤化、数字化。具体请看《皇帝新脑》-第二章《算法和图灵机》,图灵机概念是年仅24的图灵于1936年提出d的,用最精简的方式构建了一台计算机模型,而且可以证明图灵机计算不出来的,那就是算不出来。后来真正的计算机都来自于图灵机概念。

  图灵完备即图灵机的近似、图灵机的等价,一切等价于图灵机行为的计算系统、编程语言都是图灵机,像我们如今的电脑、我们使用的主流的编程语言(java、C#、C++、python等)都是图灵机。

  图灵机有个无限长的纸带,和一个有限状态自动机(状态机就是一个有向图,点是状态,边上标记读入什么字符,做什么操作,往哪个状态移动),以及一个读写头可以左右移动以及读写纸带。

  对于一个问题,你先把问题写在纸带上,然后根据读到的内容,根据状态转换的规则,转移到下一个状态。最终计算完,看到状态转移到“是”(0表示否,银河国际手机app1表示是),那么图灵机就判定是(计算结束),反之为否。其他任何计算模型都不可能比图灵机强大了。

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!