词条 | 通用图灵机 |
释义 | 能够模拟其它所有图灵机的图灵机叫做“通用图灵机”(UTM, Universal Turing Machine)。 [font color=#000000]图灵机[/font]的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,他把这样的过程看作下列两种简单的动作: 在纸上写上或擦除某个符号; 把注意力从纸的一个位置移动到另一个位置。 艾伦·图灵的“通用计算机器”("universal computing machine",或者"universal machine", "machine U", "U")是由他(1936-1937)为他的多用途单机器(计算机器)模型命名,这模型可以“运行”任何任意(但well-formed)指令序列(称为 "quintuples")。这模型被一些人例如Davis (2000) 认为是“存储程序电脑”的原点。存储程序电脑一词由约翰·冯·诺伊曼使用在他的《电子计算装置》("Electronic Computing Instrument")。这种电脑现在使用冯纽曼的名字称为冯·诺伊曼结构。 这机器作为计算模型现在称为“通用图灵机”。 [编辑] 介绍 每台图灵机从它的字母表得到字符串计算一确定的固定偏可计算函数。从外观上它的行为就像一台使用固定程式的电脑。尽管如此,我们可以把任何图灵机的动作表格编码到一条字符串。因此,我们可以建构出一台图灵机,它期待的纸带上记载有一条用以描述动作表格的字符串紧跟着一条用以描述输入的字符串,从而计算那台被编码的图灵机所计算的。图灵在1936年的文章中详细描述如此的构思。 “ 它可以表达成一台单一的特殊机器,这种型式的机器可以被塑造成去做到所有工作。事实上,它可以被塑造成如同任何其他机器的模型般工作。这种特殊机器或许可以被称呼为通用机器。 ” ──1947年的艾伦·图灵 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。