通用图灵机

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

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

介绍

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

存储程序电脑

相关条目

参考文献

  1. ^ Davis, The universal computer: the road from Leibniz to Turing (2017)
  2. ^ Arora and Barak, 2009, Theorem 1.9