通用图灵机

通用图灵机 （正體）

此条目是条目图灵机的补充。

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

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

介绍

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

“	它可以表达成一台单一的特殊机器，这种型式的机器可以被塑造成去做到所有工作。事实上，它可以被塑造成如同任何其他机器的模型般工作。这种特殊机器或许可以被称呼为通用机器。	”
—1947年的艾伦‧图灵

存储程序电脑

Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History