「集智百科精選」是一個長期專欄，持續為大家推送複雜性科學相關的基本概念和資源信息。作為集智俱樂部的開源科學項目，集智百科希望打造複雜性科學領域最全面的百科全書，歡迎對複雜性科學感興趣、熱愛知識整理和分享的朋友加入！本文是對集智百科中「組合優化」詞條的摘錄，參考資料及相關詞條請參閱百科詞條原文。本詞條由集智俱樂部眾包生產，難免存在紕漏和問題，歡迎大家留言反饋或者前往對應的百科詞條頁面進行修改，一經修改，可以獲得對應的積分獎勵噢！
圖靈機是一種數學計算模型，定義了一個抽象的機器，該機器可以根據指定的規則表在紙帶上進行操作。雖然圖靈機模型非常簡單，但是圖靈機可以模擬任何給定的計算機算法。圖靈機在一條無限長的紙帶上運行，紙帶被分割成若干個離散的單元格。機器的讀寫頭在一個單元格上「讀取」或「掃描」紙帶上的符號。然後，圖靈機根據讀取的符號和機器自身在用戶指定指令的「有限表」中的狀態，機器(i)在單元格中寫下一個符號（例如，有限字母表中的數字或字母），然後(ii)將紙帶向左或向右移動一個單元，然後(iii)根據觀察到的符號和機器自身在表中的狀態，要麼繼續執行另一指令，要麼停止計算。圖靈機是1936年由阿蘭·圖靈 Alan Turing發明，他稱之為「自動機」。通過這個模型，圖靈能夠否定地回答兩個問題:
是否存在一台機器，能夠確定其紙帶上的任意機器是否是「循環」的（例如，死機，或無法繼續其計算任務）？是否存在一種機器可以確定其紙帶上的任何任意機器是否曾經打印出一個特定的符號？因此，通過提供可以進行任意計算的非常簡單的裝置的數學描述，他能夠證明計算的一般性質，尤其是判定性問題（翻譯自德語Entscheidungsproblem, 英文譯作decision problem）的不可計算性。圖靈機證明了機械計算能力存在基本限制。雖然機械計算可以表達任意的計算，但最小設計使機械計算不適合在實踐中計算: 與圖靈機不同的是，現實世界的計算機是基於另外一種設計，即使用隨機存取存儲器 Random-access memory。圖靈完備性 Turing completeness是一個指令系統模擬圖靈機的能力。一個圖靈完備的編程語言理論上能夠表達所有計算機可以完成的任務; 如果忽略有限內存的限制，幾乎所有的編程語言都是圖靈完備的。圖靈機是一種中央處理器單元 Central Processing Unit，即CPU，控制着計算機的所有數據操作，規範及其使用順序內存來存儲數據。更具體的，圖靈機是一種能夠枚舉字母表有效字符串的機器（自動機）；這些字符串是字母遞歸可枚舉集的一部分。理想情況下，圖靈機有無限長的紙帶，其可以在上面執行讀寫操作。假設有一個「黑盒子」，圖靈機無法知道它最終是否會用給定的程序枚舉出子集中的任何一個特定字符串。這是因為停機問題 Halting Problem是不可解的，停機問題對計算的理論極限有着重大的影響。圖靈機能夠處理不受限制的語法，這意味着它能夠以無限多的方式魯棒地評價一階邏輯。通過λ運算可以證明這一點。能夠模擬任何其他圖靈機的圖靈機稱為通用圖靈機。邱奇 Alonzo Church，美國著名數學家，提出了一個更具有普適性的數學定義。他將在λ運算的工作和圖靈在正式計算機理論中的工作融合，稱為邱奇-圖靈理論。在這項工作中，他指出圖靈機確實抓住了邏輯和數學中有效方法的非正式概念，並提供了算法或「機械程序」的精確定義。研究它們的抽象特性可以使我們對計算機科學和複雜性理論有更深入的了解。物理描述在1948年的論文《智能機器 Intelligent Machinery》中，圖靈寫道他的機器包括: 以無限長紙帶的形式獲得的無限存儲容量，紙帶上標有方塊，每個方塊上可以打印一個符號。在任何時候，機器中都有一個符號，被稱為掃描符號。機器可以改變掃描的符號，其行為部分由該符號決定，但紙帶上其他地方的符號不會影響機器的行為。然而，紙帶可以在機器中來回移動，這是機器的基本操作之一。因此，紙帶上的任何符號最終都可能有一個局。
描述圖靈機在紙帶上進行機械操作的機器進行數學建模。紙帶上有符號，機器可以使用讀寫頭一次一個讀取和寫入這些符號。操作完全由一組有限的基本指令決定，例如「在狀態42中，如果看到的符號為0，則寫入1；如果看到的符號為1，則改為狀態17；在狀態17中，如果看到的符號為0，寫一個1並更改為狀態6」等。在原始的文章中（「論可計算的數字，以及對可判定行的影響」）。圖靈想象的不是一種機制，而是一種他被稱之為計算機的「人」，可以嚴格執行這些決定性的機械規則的人。
更切確地說，圖靈機由以下部分組成:
紙帶。紙帶被分成多個單元，每個緊鄰着。每個單元都包含來自某個有限字母表的一個符號。字母表中包含有一個特殊的空白符號（此處寫作「0」）和一個或者多個其他符號。假設紙帶可以任意向左/向右擴展，所以圖靈機擁有能夠支撐起計算所需的紙帶數量。沒有寫入過的單元格被假定用空白符號填充。在某些型號中，膠帶的左端標有特殊符號，磁帶向右側延伸或無限延伸。讀寫頭。讀寫頭可以在紙帶上讀寫符號，並一次將紙帶左右移動一個（有且僅有一個）單元格。在某些型號的機器中，讀寫頭移動而紙帶靜止。狀態寄存器。狀態寄存器用來存儲圖靈機的狀態，是有限多個狀態中的一個。其中有一個特殊的啟動狀態，狀態寄存器就是用它來初始化。圖靈寫道，這些狀態代替了執行計算的人通常會處於的「精神狀態」。一個有限的指令表，給定機器當前所處的狀態(qi)和它在紙帶上讀取的符號(aj)（當前讀寫頭下的符號），告訴機器依次做以下事情（對於5元組模型）：擦除或寫入一個符號（將aj替換為aj1）。
移動讀寫頭（由dk描述，如果值為'L'表示向左移動一步，'R'表示向右移動一步，'N'表示停留在原地）。
在四元組模型中，擦除或寫入符號（aj1)）和向左或向右移動讀寫頭（dk）被指定為獨立的指令。該表告訴機器（ia）擦除或寫入一個符號，或者（ib）向左或向右移動讀寫頭，然後（ii）按規定承擔相同或新的狀態，但在同一指令中不能同時執行（ia）和（ib）。在某些模型中，如果表中沒有當前符號和狀態組合的條目，那麼機器將暫停；其他模型要求填充所有條目。
機器的每一部分（即它的狀態、符號收集和在任何特定時間使用的紙帶）和它的行動（如打印、擦除和紙帶運動）都是有限的、離散的和可區分的；是無限的紙帶和運行時間給了它無限制的存儲空間。
在Hopcroft和Ullman之後，單紙帶圖靈機可以被正式定義為一個七元組M=⟨Q,Г,b,Σ,δ,q_0,F⟩，其中：bᕮГ，是空白符號（唯一允許在計算過程中的任何步驟無限頻繁地出現在紙帶上的符號）；Σ⊆Г\{b}是輸入符號集，即允許出現在初始紙帶內容中的符號集；F⊆Q是最終狀態或接受狀態的集合。初始紙帶內容被認為是接受由M如果它最終停止在一個狀態 F.δ: （Q \ F) Χ Г Χ {L, R}是一個偏函數，稱為轉移函數，其中 L 是左移，R 是右移。如果在當前狀態和當前紙帶符號上未定義，則機器停止；直觀地，轉移函數指定了從當前狀態轉移的下一個狀態，哪個符號覆蓋讀寫頭指向的當前符號，以及下一個讀寫頭運動。
此外，圖靈機還可以有拒絕狀態，使拒絕更加明確。在這種情況下，有三種可能性：接受、拒絕和永遠運行。另一種可能性是將磁帶上的最終值視為輸出。然而，如果唯一的輸出是機器最終所處的狀態（或永遠不停止），機器仍然可以有效地輸出一個較長的字符串，通過輸入一個整數，告訴它要輸出字符串的哪一位。一個相對不常見的變體允許「無移位」，比如 N，作為方向集的第三個元素{L, R}。三狀態繁忙的海狸（busy beaver）七元組是這樣的:（關於繁忙的海狸相關的資料可以搜索「圖靈機實例」了解）
δ=參見下面的狀態表（轉換函數）。
用Van Emde Boas（1990）的話來說: 「集合論對象（類似於上面的七元組描述形式）只提供了關於機器將如何運行以及它的計算將是什麼樣子的部分信息。」例如：
符號到底是什麼樣子的，需要有很多決策，也需要有一種萬無一失的方法來無窮盡地讀寫符號。左移和右移操作可能會使讀寫頭在紙帶上移動，但在實際構建圖靈機時，更實際的做法是讓紙帶在讀寫頭下來回滑動。紙帶可以是有限的，並根據需要自動延伸出空白（這是最接近數學定義的），但更常見的是將其視為在一端或兩端無限延伸，除了讀寫頭所在的明確給定的有限片段外，都會被預先填充空白。(當然，這在實踐中是無法實現的。)紙帶的長度不能是固定的，因為那不符合給定的定義，而且會嚴重限制機器可以執行的計算範圍，如果紙帶與輸入大小成正比，則為線性有界自動機的計算範圍，如果紙帶是嚴格的固定長度，則為有限狀態機的計算範圍。
其他定義文獻中的定義有時會稍有不同，以使論證或證明更容易或更清晰，但這總是以使所產生的機器具有相同的計算能力的方式進行。例如，集合可以從{L,R}改為{L,R,N}其中N（「無」或「無操作」）將允許機器停留在同一紙帶單元上，而不需要左右移動。這樣不會增加機器的計算能力。
最常見的規則是根據圖靈/戴維斯的規則，在「圖靈表」鍾永9個5元組中的一個表示每個「圖靈指令」（圖靈1936年在《The Undecidable》p.126-127）：（定義1） ：（(qi, Sj, Sk/E/N, L/R/N, qm)） 其中qi,是當前狀態，Sj是已掃描符號，Sk是打印符號，E是擦除，N是無狀態，L是向左移動，R是向右，qm 是新狀態。
其他作者(Minsky，Hopcroft和Ullman，Stone採用了另一種規定，在掃描符號Sj之後立即列出新狀態qm: (定義2): (qi, Sj, qm, Sk/E/N, L/R/N)
（當前狀態 qi, 掃描符號 Sj, 新狀態 qm, 打印 Sk/擦除 E/none N , L/right R/none N）
其中qi,是當前狀態，Sj是已掃描符號，Sk是打印符號，E是擦除，N是無狀態，L是向左移動，R是向右，qm 是新狀態。
文的其餘部分將使用「定義1」(圖靈/戴維斯規則)。
在下表中，圖靈的原始模型只允許前三行，他稱之為N1, N2, N3（參見圖靈書籍《The Undecidable》p.126）。他允許通過命名第0個S0="E"或"N"，即「擦除」或者「空白」等。但是，他不允許「不打印」，所以每個指令行都包括「打印符號Sk」或者「擦除E」。這些縮寫是圖靈在1936-1937年的原始論文之後，機器模型已經允許所有九種可能的五元組類型。
任何圖靈表（指令列表）都可以由上述九個5元組構成。由於技術原因，三個非打印或「N」指令（4、5、6）通常可以省去。
較少遇到使用4元組的情況：這些代表了圖靈指令的進一步原子化（參見Post(1947)，Boolos & Jeffrey(1974，1999)，Davis-Sigal-Weyuker(1994)）；狀態圖靈機上下文中使用的「狀態」一詞可能會引起混淆，因為它可能意味着兩件事。圖靈之後的大多數研究者都使用「狀態」來表示要執行的當前指令的名稱/指示符——即狀態寄存器的內容。但是圖靈 (1936) 在他所謂的機器「m-配置」的記錄和機器（或人）通過計算的「進展狀態」——整個系統的當前狀態——之間做出了強有力的區分。圖靈所說的「狀態公式」包括當前指令和紙帶上的所有符號：
因此，任何階段的計算進度狀態完全由指令注釋和紙帶上的符號決定。也就是說，系統的狀態可以由單個表達式（符號序列）來描述，該表達式由紙帶上的符號後跟Δ（我們假設不會出現在其他地方）和指令注釋組成。這個表達式被稱為「狀態公式」。——《The Undecidable》,圖靈，p.139–140
更早時期，圖靈在他的論文中進行了進一步的研究：他舉了一個例子，在該示例中，他把當前「m-配置」的符號（指令的標籤）和紙帶上的所有符號一起放在掃描的方塊下面（《The Undecidable》，第121頁）；他把這個稱為「完整的配置」（《The Undecidable》，第118頁）。為了將「完整配置」打印在一行，他將狀態標籤/m-配置放在掃描符號的左邊。
在Kleene（1952）中可以看到這樣的一個變體，Kleene展示了如何寫出一台機器的「狀態」的哥德爾數：他把「m-配置」符號q4放在磁帶上6個非空白方格的大致中心的掃描方格上（見本文圖靈-紙帶圖），並把它放在掃描方格的右邊。但Kleene把「q4」本身稱為「機器狀態」（Kleene，第374-375頁）。Hopcroft和Ullman把這種組合稱為「瞬時描述」，並遵循圖靈規定，把「當前狀態」（指令標籤，m-配置）放在掃描符號的左邊（第149頁）。
示例：3次「移動」後，三態2符號繁忙的海狸的總狀態（取自下圖中的示例「運行」）：
1A1
這意味着：經過三次移動後，紙帶上有......000110000......，讀寫頭正在掃描最右邊的1，狀態為A。空白（在這種情況下用「0」表示）可以成為總狀態的一部分，如圖所示。B01；紙帶上有一個「1」，但讀寫頭正在掃描它左邊的「0」（「空白」），狀態是B。圖靈機情況中，應闡明「狀態」是哪種狀態。(i)當前指令，或(ii)紙帶上的符號列表連同當前指令，或(iii)紙帶上的符號列表連同當前指令放在掃描符號的左邊或掃描符號的右邊。圖靈的傳記作者Andrew Hodges (1983:107)注意到並討論了這種混淆。圖靈機的狀態圖
「三態繁忙的海狸」圖靈機的有限狀態表示。每個圓圈代表表的一個「狀態」——一個「m-配置」或「指令」。狀態轉換的"方向"用箭頭表示。出狀態附近的標籤（如0/P,R）（在箭頭的「尾部」）指定了引起特定轉換的掃描符號（如0），後面是斜線/，接着是機器的後續「行為」，如「P打印」然後移動紙帶「R向右」。沒有普遍接受的格式存在。所顯示的規則是以McClusky（1965）、Booth（1967）、Hill和Peterson（1974）為藍本。
通常大的表格最好是留作表格（Booth，p.74）。它們更容易由計算機以表格形式模擬出來（Booth，p.74）。然而，某些概念，例如具有「復位」狀態的機器和具有重複模式的機器（參見Hill和Peterson p.244）在被視為圖紙時更容易被看到。
圖紙是否代表了對其表的改進，必須由讀者針對特定的情況來決定。詳見有限狀態機。
再次提醒讀者，這種圖表示的是在時間上凍結的表的快照，而不是計算在時間和空間上的過程(「軌跡」)。雖然繁忙的海狸的機器每次「運行」都會遵循相同的狀態軌跡，但對於可以為變量輸入「參數」提供信息的「複製」機器而言，情況並非如此。
「計算進度 "圖顯示了三態繁忙的海狸從開始到結束的計算過程中的「狀態」（指令）進度。最右邊是每一步的圖靈「完整配置」。如果機器停止並清空「狀態寄存器」和整個紙帶，則可以使用這些「配置」在其進行中的任何地方重新啟動計算（參見Turing（1936）The Undecidable 第139– 140頁）。
許多可能被認為比簡單的通用圖靈機有更多計算能力的機器，實際上並沒有更多的能力（Hopcroft和Ullman p.159, cf. Minsky(1967)）。它們可能計算得更快，或者使用更少的內存，或者它們的指令集可能更小，但是它們不能計算更多的數學函數。（邱奇-圖靈理論假設這對任何機器都是正確的：任何可以被「計算」的東西都可以被某些圖靈機器計算。）
圖靈機相當於單堆棧下推自動機 Pushdown Automaton，PDA，它通過放寬其棧中的「後進先出」要求，使其更加靈活和簡潔。此外，通過使用一個堆棧對讀寫頭左側的紙帶進行建模，使用另一個堆棧對讀寫頭右側的磁帶進行建模，圖靈機也等效於具有標準「後進先出」語義的雙堆棧PDA。
在另一個極端，一些非常簡單的模型變成了圖靈等價模型，即具有與圖靈機模型相同的計算能力。
常見的等價模型是多帶圖靈機、多道圖靈機、有輸入和輸出的機器，以及與確定型圖靈機 Deterministic Turing Machine，DTM和非確定型圖靈機 non-Deterministic Turing Machine，NDTM，後者的動作表對於每個符號和狀態組合最多只有一個條目。
只讀、右移動的圖靈機相當於 DFAs（以及通過使用NDFA到DFA轉換算法轉換的NFA）。
對於實際的和教學的意圖，等價的 寄存器機器可以作為通常的匯編編程語言使用。一個有趣的問題是：用具體編程語言表示的計算模型是否是圖靈等價的？雖然真實計算機的計算是基於有限狀態的，因此無法模擬圖靈機，但編程語言本身並不一定具有這種限制。Kirner等人在2009年的研究表明，在通用編程語言中，有些語言是圖靈完備的，而有些則不是。例如，ANSI C並不等同於圖靈機，因為ANSI C的所有實例（由於標準出於遺留的原因，故意不定義某些行為，所以可以有不同的實例）都意味着有限空間的內存。這是因為內存引用數據類型的大小，稱為指針，可以在語言內部訪問。然而，其他編程語言，如Pascal，則沒有這個功能，這使得它們在原則上是圖靈等價的。只是原則上是圖靈等價的，因為編程語言中的內存分配是允許失敗的，也就是說，當忽略失敗的內存分配時，編程語言可以是圖靈等價的，但在真實計算機上可執行的編譯程序卻不能。
早在1936年的論文中，圖靈就對「運動……完全由配置決定」的「自動機」和「選擇機」進行了區分：它的運動只是部分由配置決定……當這樣一台機器達到其中一種不明確的配置時，它不能繼續運行，直到外部操作者做出任意的選擇。如果我們使用機器來處理公理系統，就會出現這種情況。——The Undecidable，p.118
圖靈（1936）除了在腳註中描述了如何使用自動機來「找到所有希爾伯特微積分的可證明公式」，而不是使用選擇機之外，沒有做進一步的說明。他「假設選擇總是在0和1之間。那麼每個證明將由i1, i2, ..., in (i1 = 0 或 1, i2 = 0 或 1, ..., in = 0 或 1) 的選擇序列決定，因此數字 2n + i12n-1 + i22n-2 + ... +in 完全決定了證明。自動機依次執行驗證1、驗證2、驗證3，……」
這通過這種技術，一個確定型的（比如，a-）圖靈機可以用來模擬一個非確定型的圖靈機的行為; 圖靈在腳註中解決了這個問題，似乎把它從進一步的考慮中剔除了。Oracle機或o-machine是一種圖靈機器，它將計算暫停在「o」狀態，同時，為了完成計算，它「等待」「oracle」——一個未指定的實體（不是一台機器）的決定（The undecutable，p.166-168）。
正如圖靈在《The Undecidable》一書中所寫，第128頁：我們可以發明一種機器，用來計算任何可計算序列。如果向機器U提供紙帶，紙帶的開頭寫着計算機M用分號隔開的五元數組，那麼機器U將計算出與機器M相同的序列。
雖然這一發現現在被認為是很常見的，但在當時（1936年），很多人認為這是不可思議的。圖靈稱之為「通用機器」（縮寫為「U」）的計算模型被一些人（參見Davis(2000)）認為是產生存儲程序計算機概念的基礎理論的突破。
實質上包含了現代計算機的發明以及伴隨着它的一些編程技術。——Minsky（1967），P.104
就計算複雜度而言，多帶通用圖靈機與它所模擬的機器相比，只需要慢上一個對數倍。這個結果是由F.C.Hennie和R.E.Stearns在1966年得到的。(Arora and Barak，2009，定理1.9)
人們常說，圖靈機不同於簡單的自動機，它和實際的機器一樣強大，能夠執行真實程序所能執行的任何操作。在這種說法中被忽略的是，由於實際的機器只能有有限的配置，所以這裡的「真正的機器」其實只是一個有限的狀態機。另一方面，圖靈機相當於擁有無限存儲空間進行計算的機器。
有很多方法可以解釋為什麼圖靈機是實際計算機的有用模型:
凡是真正的計算機能計算的東西，圖靈機也能計算。例如，「圖靈機可以模擬編程語言中的任何類型的子程序，包括遞歸程序和任何已知的參數傳遞機制」（Hopcroft and Ullman 第157頁）。一個足夠大的FSA也可以模擬任何真正的計算機，而不用考慮IO。因此，關於圖靈機的局限性的說法也將適用於實際計算機。
區別只在於圖靈機有能力處理無限制的數據量。然而，在有限的時間內，圖靈機（像實際的機器）只能操縱處理的數據量。
像圖靈機一樣，實際的機器可以根據需要，通過獲得更多的磁盤或其他存儲介質，擴大其存儲空間。
使用較簡單的抽象模型對真機程序的描述往往比使用圖靈機的描述要複雜得多。例如，描述算法的圖靈機可能有幾百個狀態，而給定實際機器上的等效確定性有限自動機 deterministic finite automaton（DFA）卻有四千億個狀態。這使得DFA的表示方式無法分析。
圖靈機描述的算法與它們使用的內存多少無關。目前任何機器所擁有的內存都有一個極限，但這個極限可以在時間上任意上升。圖靈機允許我們對算法做出聲明，這些聲明（理論上）將永遠成立，而不考慮傳統計算機架構的進步。
圖靈機簡化了算法的表述。在圖靈機上運行的算法通常比在實際機器上運行的算法更通用，因為它們有任意精度的數據類型可用，而且永遠不必處理意外情況（包括但不限於內存耗盡）。
計算複雜性理論圖靈機的一個局限性在於，其不能很好地模擬特定排列的優勢。例如，現代存儲程序計算機實際上是一種更具體的抽象機器的實例，這種抽象機器被稱為隨機存取存儲程序機器或 RASP機器模型。與通用圖靈機一樣，RASP將其「程序」存儲在有限狀態機的「指令」之外的「內存」中。與通用圖靈機不同的是，RASP具有無限數量可區分的、有編號但無限制的「寄存器」——可以包含任何整數的內存「單元」（參見Elgot和Robinson(1964)，Hartmanis(1971)，特別是Cook-Rechow(1973)）；RASP的有限狀態機可以間接尋址（例如，一個寄存器的內容可以用作另一個寄存器的地址），因此當圖靈機被用作約束運行時間的基礎時，可以證明某些算法的運行時間有一個「假下限」（由於圖靈機的假簡化假設）。這方面的一個例子是二進制搜索，當使用RASP計算模型而不是圖靈機模型時，可以證明這種算法的運行速度更快。
並發性圖靈機的另一個局限是，其不能很好地模擬並發。例如，一個始終保持非確定性的圖靈機在空白紙帶上開始計算的整數大小是有限制的。相比之下，有一些沒有輸入的始終保持一致的並發系統，可以計算出無界大小的整數。(可以用本地存儲創建一個初始化為0的進程，它同時向自己發送一個「停止」和一個「運行」的消息。當它收到一個「運行」信息時，它的計數增加1，並向自己發送一個去信息。當它收到一個「停止」消息時，它就停止，在它的本地存儲區有一個無限制的數字）。
交互在計算機的早期，計算機的使用通常僅限於批處理，即非交互式任務，每個任務從給定的輸入數據中產生輸出數據。可計算性理論研究從輸入到輸出的函數的可計算性，圖靈機就是為此而發明的，其反映了這種做法。自20世紀70年代以來，計算機的交互式使用變得更加普遍。原則上，可以通過讓外部代理與圖靈機同時從紙帶中讀出並寫入紙帶的方式進行建模，但這很少與交互的實際發生方式相吻合；因此，在描述交互性時，通常首選I/O自動機等替代程序。
歷史背景：計算機器羅賓•甘迪 Robin Gandy，1919-1995,是圖靈（1912-1954）的學生，也是他一生的朋友，他將「計算機器」這一概念的淵源追溯到查爾斯•巴貝奇 Charles Babbage（大約1834年），並提出了「巴貝奇論」：整個發展和分析的操作現在都可以由機器來執行。（italics in Babbage as cited by Gandy, p.54）
算術函數+，-，×，其中「-」表示「適當的」減法，即滿足某種條件，比如y≥x，x-y=0。
任何運算序列都是一個運算。
操作的迭代（重複n次操作p）。
條件迭代（以測試t的「成功」為條件重複n次操作p）。
條件轉移（即有條件的「goto」）。
Gandy指出: 「可由(1)、(2)和(4)計算出來的函數恰恰是那些圖靈可計算的函數。」(p.53)。他引用了其他關於「通用計算機」的理論，包括珀西•盧德蓋特 Percy Ludgate， 1909年、萊昂納多•托雷斯•奎維多 Leonardo Torres y Quevedo，1914年、莫里斯•d』奧卡涅 Maurice d'Ocagne，1922年、路易斯•庫夫尼納爾 Louis Couffignal，1933年、萬尼瓦•布什V annevar Bush，1936年、霍華德•艾肯 Howard Aiken，1937年。然而：重點是對一個固定的可迭代的算術運算序列進行編程。條件性迭代和條件性轉移對於計算機的一般理論的根本重要性沒有得到承認……——Gandy，第55頁判定問題: 希爾伯特1900年提出的第10號問題關於著名數學家大衛·希爾伯特 David Hilbert在1900年提出的希爾伯特問題中，第10號問題的一個方面浮動了近30年，才被準確地框定下來。希爾伯特對10號問題的原始表述如下：10. Diophantine方程的可解性的確定。給出一個具有任意數量的未知量和有理積分係數的Diophantine方程。設計一個過程，根據這個過程可以在有限的操作中確定該方程是否可以用有理整數來解。當我們知道一個程序，允許任何給定的邏輯表達式通過有限的多次操作來決定其有效性或可滿足性時，判定問題（一階邏輯的決定問題）就解決了……判定問題必須被認為是數理邏輯的主要問題。——2008年，德爾肖維茨 Dershowitz和古列維奇 Gurevich引用了此譯文和德文原文。
到了1922年，「判定問題」的概念有了進一步的發展，Behmann指出：判定問題的一般形式如下:需要一個相當明確的、普遍適用的處方，它將允許人們在有限的步驟中決定一個給定的純邏輯論斷的真假……——Gandy，第57頁，引用Behmann的話。
Behmann指出：一般問題相當於決定哪些數學命題是真的問題。如果能夠解決判定問題，那麼人們就會有一個「解決許多（甚至所有）數學問題的程序」。
1928年的國際數學家大會，希爾伯特把他的問題描述的非常的細緻。第一，數學是完整的嗎？第二，數學是一致的嗎？第三，數學是可判定的嗎？」1930年，在希爾伯特發表退休演講的同一次會議上，庫爾特·哥德爾 Kurt Gödel回答了前兩個問題；而第三個問題（判定問題）不得不等到上世紀30年代中期。
問題在於，要回答這個問題，首先需要對「明確的通用規則」下一個精確定義。普林斯頓大學的教授阿朗佐•丘奇 Alonzo Church將其稱為「有效可計算性」，而在1928年並不存在這樣的定義。但在接下來的6-7年裡，埃米爾•波斯特 Emil Post拓展了他的定義，即一個工人按照一張指令表從一個房間移動到另一個房間書寫和擦除標記（1936），邱奇和他的兩個學生Stephen Kleene和j.B. Rosser利用邱奇的λ微積分和哥德爾的遞歸理論也是如此。丘奇的論文（發表於1936年4月15日）表明，判定問題確實是「無法決策的」，比圖靈早了將近一年（圖靈的論文1936年5月28日提交，1937年1月發表）。與此同時，波斯特在1936年秋天提交了一篇短文，所以圖靈至少比波斯特更有優先權。當丘奇評審圖靈的論文時，圖靈有時間研究丘奇的論文，並在附錄中添加了一個草圖，證明邱奇的λ微積分和他的機器可以計算同樣的函數。
但邱奇所做的是完全不同的事情，而且在某種意義上是較差的。……圖靈的構造更直接，並提供了最初原則的論據，從而彌補了邱奇證明中的空白。——Hodges，第112頁
波斯特只是提出了一個可計算性的定義，並批評了邱奇的「定義」，但沒有證明任何事情。
阿蘭圖靈的機器1935年春天，圖靈作為英國劍橋大學國王學院的一名年輕碩士生，接受了這個挑戰；他受到邏輯學家紐曼 Newman的講座的鼓舞，並從他們那裡了解了哥德爾的工作和判定問題。在圖靈1955年的訃告中，紐曼寫道: 對於「什麼是『機械』過程」？圖靈回答了一個特有的答案「可以由機器完成的事情」，接着他開始着手分析計算機的一般概念。——Gandy，第74頁
Gandy表示：我想，但我不知道，圖靈從他工作的一開始，就把證明判定問題的不可解性作為他的目標。1935年夏天，他告訴我，當他躺在格蘭切斯特草地的時候，他完成了這篇論文的構想。這個「構想」可能是他對計算的分析，也可能是他意識到有一個普遍的機器，因此有一個對角線論證來證明不可解性。——同上，第76頁
儘管Gandy認為Newman的上述言論有「誤導性」，但這一觀點並不為所有人所認同。圖靈一生都對機器有着濃厚的興趣：「阿蘭（圖靈）從小就夢想發明打字機；（他的母親）圖靈夫人有一台打字機；他很可能一開始就問自己，把打字機稱為『機械的』是什麼意思」（Hodges p.96）。在普林斯頓攻讀博士學位時，圖靈製造了一個布爾邏輯乘法器（見下文）。他的博士論文題為「基於序數的邏輯系統」，包含了「可計算函數」的定義：上面說過，「如果一個函數的值可以通過某種純粹的機械過程找到，那麼它就是有效的可計算的」。我們可以從字面上理解這句話，用純粹的機械過程來理解可以由機器來完成的過程。我們有可能以某種正常形式對這些機器的結構進行數學描述。這些想法的發展導致了作者對可計算函數的定義，以及對可計算性與有效可計算性的認同。要證明這三個定義（第三個是λ-微積分）是等價的並不困難，雖然有些麻煩。——圖靈（1939）在《The Undecidable》一書中，第160頁
當圖靈回到英國後，他負責破解名為「英格瑪」的加密機創造的德國密碼；他還參與了ACE（自動計算引擎）的設計。「圖靈的ACE建議實際上是自成一體的，其根源不在於EDVAC（美國的倡議），而在於他自己的通用機器」（Hodges p.318）。關於被Kleene（1952年）命名為 「圖靈論文」的起源和性質的爭論仍在繼續。但是，圖靈用他的計算機模型所證明的東西出現在他的論文中「關於可計算數及其在Entscheidungs型問題中的應用」。
希爾伯特-判定問題不可能有解……因此我建議，不可能有一個一般的過程來確定函數微積分K的一個給定公式U是否可證明，也就是說，不可能有一台機器在提供任何一個公式U的情況下，最終會說出U是否可證明。——摘自圖靈的論文，詳見《The Undecidable》，第145頁
圖靈的例子（他的第二個證明）：如果有人要求用一般程序來告訴我們：「這台機器是否曾經打印過0」，這個問題就是「無法確定的」。
1937-1970「數字計算機」「計算機科學」的誕生1937年，圖靈在普林斯頓大學寫博士論文時，從零開始建立了一個數字（布爾邏輯）乘法器，自製了機電繼電器（Hodges p.138）。「艾倫的任務是將圖靈機的邏輯設計體現在一個由繼電器操作的開關網絡中……」（Hodges p.138）。德國（Konrad Zuse，1938年）和美國（Howard Aiken，1937年）都在朝着同一個方向努力，他們的勞動成果被軸心國和盟國的軍隊在二戰中使用。在20世紀50年代初至中期，Hao Wang和Marvin Minsky將圖靈機簡化為一種更簡單的形式（它是 Martin Davis的後圖靈機的前身）；與此同時，歐洲研究人員將這種新型電子計算機簡化為一種類似於計算機的理論物體，相當於現在所說的「圖靈機」。在20世紀50年代後期和60年代初期，Melzak和Lambek（1961）、Minsky（1961）和Shepherdson and Sturgis（1961）等人不約而同地展開進一步的研究，推進了歐洲的工作，並將圖靈機簡化為一個更友好的、類似計算機的抽象模型，稱為計數器；Elgot和Robinson（1964）、 Hartmanis（1971）、Cook 和 Reckhow（1973）將這項工作進一步推進到寄存器和隨機存取機器模型——但基本上所有這些都只是帶有類似算術指令集的多帶圖靈機。
1970年至今：作為計算模型的圖靈機如今，計數器、寄存器和隨機存取機以及它們的先驅圖靈機仍然是理論家們研究計算理論問題的首選模型。特別是，計算複雜性理論也使用了圖靈機。
根據人們在計算中喜歡操作的對象（非負整數或字母數字串等），有兩種模型在基於機器的複雜性理論中獲得了主導地位：離線多帶圖靈機——它代表了面向字符串計算的標準模型，以及Cook和Reckhow提出的隨機存取機(RAM) ，它是理想化的馮諾依曼式計算機的模型。——van Emde Boas 1990:4 只有在算法分析的相關領域，這個角色才能被RAM模型所取代。——van Emde Boas 1990:4
集智文章推薦1931年，天才數學家圖靈提出了著名的圖靈機模型，它奠定了人工智能的數學基礎。1943年，麥克洛克 & 皮茨（McCulloch & Pitts）兩人提出了著名的人工神經元模型，該模型一直沿用至今，它奠定了所有深度學習模型的基礎。那麼，這兩個開山之作究竟是怎樣一種相愛相殺的關係呢？天才數學家馮諾依曼指出，圖靈機和神經元本質上雖然彼此等價，我們可以用圖靈機模擬神經元，也可以用神經元模擬圖靈機，但是它們卻位於複雜度王國中的不同領地。神經網絡代表了一大類擅長並行計算的複雜系統，它們自身的結構就構成了對自己最簡潔的編碼；而圖靈機則代表了另一類以穿行方式計算的複雜系統，這些系統以通用圖靈機作為複雜度的分水嶺：一邊，系統的行為可以被更短的代碼描述；另一邊，我們卻無法繞過複雜度的溝壑。而先進的深度學習研究正在試圖將這兩類系統合成為一個：神經圖靈機。
課程推薦
圖靈機
https://campus.swarma.org/course/1155
本課程將圍繞圖靈機，詳細介紹圖靈機的定義、圖靈機的計算、圖靈機框架的模擬、通用圖靈機、以及圖靈停機問題，說明算法的上界。人工智能2020
https://campus.swarma.org/course/1153
本課程為北京師範大學系統科學學院張江教授開設的研究生課程《人工智能》課程回放。課程偏重理論，輔以編程實踐，將粗粒度的梳理人工智能重要的理念、算法、模型。前面會包含一些人工智能之前的理論計算機模型，圖靈機等，後面系統從兩方面講解，一是符號派的人工智能，包括搜索、推理、表示等；二是連接派的人工智能，機器學習，強調理論機器學習基礎。文章推薦
分子計算：通向化學圖靈機的途徑。
https://pattern.swarma.org/paper?id=9207a15c-9b1d-11ea-abd6-0242ac1a0005
為了順應快速增長的信息存儲和處理需求，需要新的計算策略。分子計算的想法（即通過分子、超分子或生物分子方法進行基本計算，而不是通過電子方法）長期以來一直吸引着研究人員。使用分子和(生物)大分子進行計算的前景並非沒有先例。自然中充滿了以高效率、低能量成本和高密度信息編碼來處理和存儲數據的示例。根據通用計算方法運行的計算機的設計和組裝，例如圖靈機中的計算機，未來可能會以化學的方式實現。從這個角度來看，本文章重點介紹了到目前為止已經設計和合成的分子和(生物)大分子系統，目的是將它們用於計算目的；還提出了分子圖靈機的藍圖，它基於一個催化裝置，它沿着聚合物帶滑動，在移動時，以氧原子的形式在這條帶上打印二進制信息。使用圖靈機的圖靈模式：出現和低層次結構形成。
https://pattern.swarma.org/paper?id=14ecc15e-8860-11ea-b132-0242ac1a000b
儘管阿蘭·圖靈(Alan Turing)在1952年發表的關於形態發生的論文中提出了常微分方程的反應擴散模型，反映了他對數學生物學的興趣，但他從未被認為接近過細胞自動機的定義。然而，他對形態發生的處理，特別是他發現的與對稱破缺導致的某些形式的不均勻分布有關的困難，是將他的普遍計算理論與他的生物模式形成理論聯繫起來的關鍵。建立這樣的聯繫並不能克服圖靈所擔心的特殊困難，無論如何，這個問題已經在生物學上得到了解決。但相反，這裡開發的方法抓住了圖靈最初關心的問題，並通過算法概率的概念為更一般的問題提供了一個低級解決方案，從而將圖靈模式形成和通用計算這兩個他對科學最重要的貢獻聯繫在了一起。本文將展示使用此方法的一維模式的實驗結果，而不會損失對n維模式泛化的一般性。作為集智百科項目團隊的成員，本文內容由Solitude、Langenfeng、Swarma編譯，AvecSally、ZQ審校，SyouTK編輯。我們也為每位作者和志願者準備了專屬簡介和個人集智百科主頁，更多信息可以訪問其集智百科個人主頁。以上內容都是我們做這項目的起點，作為來自不同學科和領域的志願者，我們建立起一個有效的百科團隊，分配有審校、翻譯、編輯、宣傳等工作。我們秉持：知識從我而來，問題到我為止的信念，認真負責編撰每一個詞條。
在這裡從複雜性知識出發與夥伴同行，同時我們希望有更多志願者加入這個團隊，使百科詞條內容得到擴充，並為每位志願者提供相應獎勵與資源，建立個人主頁與貢獻記錄，使其能夠繼續探索複雜世界。
如果你有意參與更加系統精細的分工，掃描二維碼填寫報名表，我們期待你的加入！
加入集智，一起複雜！
點擊「閱讀原文」，閱讀詞條圖靈機原文與參考文獻
留言列表