主题
Search

通用图灵机

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
UniversalTuringMachine7-4Rules

一种 图灵机，通过使用有限长度的输入带进行适当的编程，可以充当任何 图灵机。在图灵的开创性论文中，他本人给出了通用图灵机的第一个构造（Turing 1937, 1938）。Shannon (1956) 表明，只要使用足够的状态，两种颜色就足够了。Minsky (1962) 发现了一种 7 状态 4 色的通用图灵机，如上图所示 (Wolfram 2002, p. 706)。请注意，第 20 条规则规定图灵机应停止，如头部保持静止且不改变其状态所示。转换为 2 色机器后，Minsky 的通用图灵机需要 43 个状态。

关于小型通用图灵机的出版物相对较少，直到 Rogozhin (1996) 发现了状态数 (m,n) 和颜色数 m 和 n 由 (24, 2)、(10, 3)、(7, 4)、(5, 5)、(4, 6)、(3, 10) 和 (2, 18) 给出的示例 (Wolfram 2002, p. 1119)。

UniversalTuringMachine2-5Rules

Wolfram (2002, p. 707) 发现了一种 2 状态 5 色的通用图灵机，如上图所示。此示例具有任何其他已知通用图灵机的最小乘积 mn=10。然而，很可能存在更小的示例。

UniversalTuringMachine2-4Rules
UniversalTuringMachine2-3Rules

Wolfram (2002, pp. 708-709) 确定的四个 2 状态 4 色和 14 个本质上等效的 2 状态 3 色机器很可能是通用的，尽管这似乎难以证明。2007 年 5 月 14 日，Wolfram Research 和 Stephen Wolfram 宣布为证明该图灵机实际上是通用的提供 25,000 美元的现金奖励。2007 年 10 月 24 日，Alex Smith 用成功的证明获得了该奖项 (Smith 2020)。

另请参阅

蔡廷常数, 停机问题, 图灵机, 通用细胞自动机, 通用性

使用 Wolfram|Alpha 探索

参考文献

Minsky, M. L. "Some Universal Elements for Finite Automata." Automata Studies. Princeton, NJ: Princeton University Press, pp. 117-128, 1956.Minsky, M. L. "Size and Structure of Universal Turing Machines Using Tag Systems." Proc. Sympos. Pure Math. 5, 229-238, 1962.Ord, T. "Hypercomputation: Computing More Than the Turing Machine." 25 Sep 2002. http://arxiv.org/abs/math.LO/0209332.Penrose, R. The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford: Oxford University Press, pp. 51-57, 1989.Rogozhin, Yu. V. "Seven Universal Turing Machines." Mat. Issled., No. 69, 76-90, 1982.Rogozhin, Yu. V. "A Universal Turing Machine with 10 States and 3 Symbols." Izv. Akad. Nauk Respub. Moldova Mat., No. 4, 80-82 and 95, 1992.Rogozhin, Yu. "Small Universal Turing Machines." Theoret. Comput. Sci. 168, 215-240, 1996.Shannon, C. E. "A Universal Turing Machine with Two Internal States." Automata Studies. Princeton, NJ: Princeton University Press, pp. 157-165, 1956.Smith, A. "Universality of Wolfram's 2, 3 Turing Machine." Complex Systems 29, 1-44, 2020. Turing, A. M. "On Computable Numbers, with an Application to the Entscheidungsproblem." Proc. London Math. Soc. Ser. 2 42, 230-265, 1937. Reprinted in The Undecidable (Ed. M. David). Hewlett, NY: Raven Press, 1965.Turing, A. M. "Correction to: On Computable Numbers, with an Application to the Entscheidungsproblem." Proc. London Math. Soc. Ser. 2 43, 544-546, 1938.Wolfram Research and Wolfram, S. "The Wolfram 2,3 Turing Machine Research Prize." http://www.wolframscience.com/prizes/tm23/.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 706-711 and 1119, 2002.

在 Wolfram|Alpha 上引用

通用图灵机

请引用为

Weisstein, Eric W. "通用图灵机。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/UniversalTuringMachine.html

主题分类