通用图灵机

✍ dations ◷ 2025-08-23 09:51:25 #艾伦图灵,图灵机

通用图灵机(universal Turing machine,又称Machine U)是一种图灵机,由艾伦·图灵在1936年发明。这种多用途单机器(计算机器)模型可以“运行”任何任意(但well-formed)指令序列(称为 "quintuples")。这模型被一些人例如Davis (2000) 认为是“存储程序电脑”的原点。存储程序电脑一词由约翰·冯·诺伊曼使用在他的《电子计算装置》("Electronic Computing Instrument")。这种电脑现在使用冯·诺伊曼的名字称为冯·诺伊曼结构。

这机器作为计算模型现在称为“通用图灵机”。

每台图灵机从它的字母表得到字元串计算一确定的固定偏可计算函数。从外观上它的行为就像一台使用固定程式的电脑。尽管如此,我们可以把任何图灵机的动作表格编码到一条字元串。因此,我们可以建构出一台图灵机,它期待的纸带上记载有一条用以描述动作表格的字元串紧跟着一条用以描述输入的字元串,从而计算那台被编码的图灵机所计算的。图灵在1936年的文章中详细描述如此的构思。

相关

  • 杨朵症候群杨朵症候群(Yentl Syndrome)是指因女性心肌梗死的症状和男性不同,所造成的问题。许多心肌梗死的医学研究主要研究男性心肌梗死的症状,而女性的心肌梗死症状可能和男性不同,因此女
  • 华氏 (消歧义)华氏一词可指:
  • 椭球体椭球是一种二次曲面,是椭圆在三维空间的推广。椭球在xyz-笛卡儿坐标系中的方程是:其中a和b是赤道半径(沿着x和y轴),c是极半径(沿着z轴)。这三个数都是固定的正实数,决定了椭球的形状
  • 法兰西学术院法兰西学术院(法语:Académie française)是法国的一所学术机构,是法兰西学会下属的五个学术院之一,是五个学术院中历史最悠久、名气最大的学术权威机构,当选法兰西学院院士是极高
  • 小行星列表以下列举了太阳系中一些值得关注的小行星,此列表也包括木星轨道以外的小行星。如需更完整的列表,请参见依编号排列的小行星列表。备注:任何小行星要在其轨道数据被准确得知以后
  • 灭火救火,是指扑灭火灾的行动。消防一词是和制汉语,源自日本江户时代的消防组织及其成员“火消し”,其结合灭火(消火しょうか)与防灾(防火ぼうか)的概念,为日本明治维新时期所创造,中
  • 蜡膜有些鸟的角质喙与前头部之间的连接是柔软的皮肤,称为蜡膜,有的蜡膜遮住了鼻,鼻孔从下侧开口。有些鹦鹉如金刚鹦鹉的蜡膜被覆羽毛,而有些鹦鹉如虎皮鹦鹉和鸽、鸮的蜡膜是裸露的。
  • 成见威胁成见威胁(英语:stereotype threat)是指一个人在某种环境里,会担忧或焦虑自己的行为,将会验证那些对于自己所属社会群体的负面刻板印象,而这种焦虑将会影响该人的表现,使得他的表现
  • 古斯·格里森维吉尔·伊万·“古斯”·格里森(英语:Virgil Ivan "Gus" Grissom,1926年4月3日-1967年1月27日),前美国空军中校及美国国家航空航天局宇航员,执行过水星-红石4号、双子星座3号以及
  • 严岛坐标:34°16′24.2″N 132°18′30.06″E / 34.273389°N 132.3083500°E / 34.273389; 132.3083500严岛(日语:厳島/いつくしま  */?)是位于日本濑户内海广岛湾(日语:広島湾)西部