研究计划执行情况概述 图灵机 图灵机-概述,图灵机-研究简况

图灵机就是指一种抽象的机器,这种机器有一条无限长的纸带,纸带分成了一个一个的小方格,而每个方格有不同的颜色。有一个机器头在纸带上不断移来移去。机器头有一组内部状态,还有一些固定的程序。在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。这个在概念上如此简单的机器,理论上却可以计算任何直观可计算的函数。图灵机作为计算机的理论模型,在有关计算理论和计算复杂性的研究方面得到广泛的应用。

图灵机_图灵机 -概述

英国数学家A.M.图灵提出的一种抽象计算模型,用来精确定义可计算函数。图灵机由一个控制器、一条可无限延伸的带子和一个在带子上左右


图灵机移动的读写头组成。这个在概念上如此简单的机器,理论上却可以计算任何直观可计算的函数。图灵机作为计算机的理论模型,在有关计算理论和计算复杂性的研究方面得到广泛的应用。

图灵机_图灵机 -研究简况

由于图灵机以简明直观的数学概念刻划了计算过程的本质,自1936年提出以来,有关学者对它进行了广泛的研究。C.E.仙农证明每一个图灵机等价于仅有两个内部状态的图灵机,王浩证明每个图灵机可由具有一条只读带和一条只有两个符号的存储带的图灵机模拟。人们还证明,图灵机与另一抽象计算模型──波斯特机器在计算能力上是等价的(见波斯特对应问题)。
人们还研究了图灵机的各种变形,如非确定的图灵机、多道图灵机、多带图灵机、多维图灵机、多头图灵机和带外部信息源的图灵机等。除极个别情形外,这些变形并未扩展图灵机的计算能力,它们计算的函数类与基本图灵机是相同的,但对研究不同类型的问题提供了方便的理论模型。例如,多带图灵机是研究计算复杂性理论的重要计算模型。人们还在图灵机的基础上提出了不同程度地近似于现代计算机的抽象机器,如具有随机访问存储器的程序机器等。

图灵机_图灵机 -基本结构和功能

图灵机的控制器具有有限个状态。其中有两类特殊状态:开始状态和结束状态(或结束状态集合)。图灵机的带子分成格子,右端可无限延伸,每个格子上可以写一个符号,图灵机有有限个不同的符号。图灵机的读写头可以沿着带子左右移动,既可扫描符号,也可写下符号。


图灵机在计算过程的每一时刻,图灵机处于某个状态,通过读写头注视带子某一格子上的符号。根据当前时刻的状态和注视的符号,机器执行下列动作:转入新的状态;把被注视的符号换成新的符号;读写头向左或向右移动一格。这种由状态和符号对偶决定的动作组合称为指令。例如指令q1ai│ajq2L表示当机器处在状态q1下注视符号ai时,将ai换成符号aj,转入新的状态q2,读写头左移一格。决定机器动作的所有指令表称为程序。结束状态或指令表中没有的状态、符号对偶,将导致停机。
在每一时刻,机器所处状态、带子上已被写上符号的所有格子以及机器当前注视的格子位置,统称为机器的格局。图灵机从初始格局出发,按程序一步步把初始格局改造为格局的序列。此过程可能无限制继续下去,也可能遇到指令表中没有列出的状态、符号组合或进入结束状态而停机。在结束状态下停机所达到的格局是最终格局,此最终格局(如果存在)就包含机器的计算结果。

图灵机接受语言

图灵机(简记为 T)可作为接受语言的装置,它所接受的语言L恰是所有这样的符号串ω的集合:如果把符号串ω记录在T的带子上,开始工作时T处于初始状态q0,读写头处于带子最左端,则经过有限步之后,T进入某个结束状态q。被图灵机接受的语言类也就是递归可枚举集,或 O型语言(见形式语言理论)。

图灵机产生语言

研究计划执行情况概述 图灵机 图灵机-概述,图灵机-研究简况
图灵机作为语言的产生装置,它在带子上枚举出该语言中所有的字。如果这个语言是无限的,这个枚举过程就是无穷的。图灵机产生的语言恰是递归可枚举集。图灵机按字长增长的顺序产生的语言,恰是递归集。

图灵机计算函数

设机器带子上的输入符号串为自然数n的编码。如果机器从这样的带子出发,到达结束状态时,带子上符号串已改造为m的编码,则称机器计算了函数f(n)=m。如果一个函数以自然数为值域和定义域,并且有一个图灵机计算它,则称此函数为“可计算函数“。
由于图灵机的带子是可以向右无限延伸的,所以图灵机的存储空间和计算时间都是可无限制增加的。因此,图灵机是一般算法概念的精确化,即任何算法均可由适当的图灵机模拟。人们尚未发现一个直观可以计算的函数不能由图灵机来计算。而且,已有的关于直观可计算函数的另一些精确化定义,如递归函数、λ可定义函数等,都等价于图灵机定义的可计算函数。

图灵机_图灵机 -通用图灵机

已经证明,存在一个图灵机U,它可以模拟任何其他的图灵机T,这样的U称为通用图灵机。U的带子上记录着被模拟机器T的指令描述,也记录着T的问题数据。在工作过程中,U根据输入带上记录的T的指令,模拟T的动作,处理问题的数据。这样,U可以模拟任何计算过程。

图灵机_图灵机 -停机问题

图灵机根据机器的程序处理初始格局。有的初始格局可能导致停机,有的则导致无限的格局序列。停机问题是:是否存在一个算法,对于任意给定的图灵机都能判定任意的初始格局是否会导致停机。已经证明,这样的算法是不存在的,即停机问题是不可判定的。
停机问题是研究许多不可判定问题的基础,人们往往把一个问题的判定归结为停机问题:“如果问题 A可判定,则停机问题可判定。”从而证明问题 A的不可判定性。停机问题有多种不同的叙述方式和证明方法,它们分别适用于具有不同特征的问题。

  

爱华网本文地址 » http://www.413yy.cn/a/8104060103/167263.html

更多阅读

100周年记图灵:被成见迫害的计算机之父

【感悟】阿兰·麦席森·图灵Alan MathisonTuring籍贯:英国伦敦民族: 英格兰生日:1912年6月23日教育:剑桥大学国王学院职业:数学家及计算机逻辑学家,他被视为计算机科学之

艾尔·图灵 图灵机

苹果电脑公司以那个咬了一口的苹果作为其商标图案,就是为纪念这位伟大的人工智能领域的先驱者——艾兰·图灵。艾兰·图灵英国数学家、逻辑学家,被称为计算机科学之父、人工智能之父。1931年图灵进入剑桥大学国王学院,毕业后到美国普林

计算机世界第一人:艾兰·图灵

计算机世界第一人:艾兰·图灵(1)_wxl P>·摘要:他的英年早逝,像他横溢的才华一样,令世界吃惊与难以置信。生命虽然短暂,但那传奇的人生,丰富多彩的创造力和智慧而深邃的思想,使他犹如一颗耀眼的明星,持续地照耀着人间后世在科学的浩瀚太空

图灵奖得主姚期智印象 姚期智

标 题: zz 图灵奖得主姚期智印象发信站: 华南木棉BBS ,转信图灵奖得主姚期智印象刘冬梅姚期智,祖藉湖北孝感,1946年12月24日出生于上海,幼年随父母移居台湾。1967年,姚期智毕业于台湾大学,之后赴美国深造。1972年获哈佛大学物理学博士学

谜一样的艾伦·图灵 艾伦图灵传txt下载

谜一样的艾伦·图灵艾伦·图灵图灵机计算机之父同性恋者艾伦·图灵于1912年6月23日出生于伦敦,1954年6月7日逝于曼彻斯特,活了不到42岁。纪念6月23日,当百度首页显示端午赛龙舟动画之际,谷歌首页的涂鸦显示的则是一条被分成很多小格的纸

声明:《研究计划执行情况概述 图灵机 图灵机-概述,图灵机-研究简况》为网友何时懂得分享!如侵犯到您的合法权益请联系我们删除