主題
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 日， 和 Stephen Wolfram 宣佈為證明該圖靈機實際上是通用的提供 25,000 美元的現金獎勵。2007 年 10 月 24 日，Alex Smith 用成功的證明獲得了該獎項 (Smith 2020)。

另請參閱

蔡廷常數, 停機問題, 圖靈機, 通用細胞自動機, 通用性

使用 探索

參考文獻

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. 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.

在 上引用

通用圖靈機

請引用為

Weisstein, Eric W. "通用圖靈機。" 來自 Web 資源。 https://mathworld.tw/UniversalTuringMachine.html

主題分類