今天的程序員面臨着财富的尴尬。軟件工具豐富豐富，硬件強大而便宜。衡量軟件工具不斷增加的複雜性和複雜性的一種簡單方法是查看生成“Hello, world！”需要什麼。程序。

在 C 和 Unix™ 的早期，它隻需要幾行源代碼。現在，使用 Windows C/C 編譯器或其他 GUI 編程工具，即使是生成一個簡單的“hello world”程序，也涉及數百行應用程序程序員很少看到的支持代碼。

編程環境可能很大，因為今天可用的機器随着價格的下降而功率上升。工具越來越容易使用，調試器越來越複雜。現在是成為程序員的好時機，但有時我們會被軟件工具和硬件平台的強大和優雅所蒙蔽。

有時值得退後一步，從第一原則的角度看待這個世界。物理學家（至少是優秀的物理學家）從第一原理來看世界。在數學中，第一性原理被稱為公理。

擺脫編寫程序的日常工作并根據公理來思考計算機是令人耳目一新的。公理與編寫計算機程序有什麼關系？試着回答這個簡單的問題：什麼是計算？

什麼是計算？答案是：圖靈機中導緻停止狀态的配置序列稱為計算。這意味着如果你的算法在圖靈機上成功運行，它就是一個計算。如果不是，那麼它不是計算！

我們所知道的世界在 1936 年發生了變化。在胡佛水壩開始發電的同一年，雪莉·坦普爾 (Shirley Temple) 成為票房冠軍，一位名叫艾倫·圖靈 (Alan Turing) 的 24 歲英國人完成了一篇名為“關于可計算數字”的論文應用于Entsheidungsproblem。

Entsheidungsproblem 是可判定性問題的德語表達方式。

什麼是可判定性？可判定性意味着“可以開發一種算法來解決産生是或否答案的特定問題嗎？”

為什麼對可判定性如此惡臭？從 1910 年開始，一直持續到 1913 年，阿爾弗雷德·諾斯·懷特黑德 (Alfred North Whitehead) 和伯特蘭·羅素 (Bertrand Russel) 發表了被認為是開創性數學著作之一的《數學原理》。在這三卷集中，懷特黑德和羅素試圖将整個數學簡化為形式邏輯的一個子集。他們打算證明數學是完整的。在這種情況下，完整一詞的含義意味着可以通過某些機械方式生成證明或公式。根據已知為真的公理，可以将其他細節和條件添加到機械算法中以創建新的證明。這種觀點，就像在牛頓物理學中一樣，提供了一種類似發條的、确定性的世界觀。1931 年，庫爾特·哥德爾提出了他的不完備性定理，這有效地表明，我們作為數學真理所持有的基本概念無法被正式證明。這種不完整性甚至适用于簡單的數字。這打破了懷特黑德和羅素關于磨出機械證明的概念，進而動搖了數學的基礎。如果構建問題的基礎不完整，怎麼可能有決定性？

在他有點晦澀的論文中，圖靈描述了一種抽象的通用計算機，現在稱為圖靈機。

事實證明，沒有比圖靈機更強大的機器，無論是理論上的還是現實的。

圖靈機是現代計算機科學的基石。正如他從一開始就堅持的那樣，圖靈的抽象機器實際上是可以建造的。

不幸的是，1936年也是4000名納粹軍隊悄悄潛入萊茵蘭，占領凡爾賽條約規定的非軍事區的一年，預示着二戰的開始。

1940 年，英國處于戰争狀态，德國 U 型潛艇無情地摧毀了護航船，圖靈（和其他有才華的數學家）被英國高級指揮部征召，幫助破解德國的軍事密碼。

幸運的是，從一艘正在下沉的 U 艇中捕獲了一台名為“Enigma”的德國秘密密碼機。憑借捕獲的 Enigma 的額外獎勵，圖靈破解了所謂的牢不可破的 Enigma 密碼，并在盟軍赢得北大西洋戰争的過程中發揮了重要作用。

戰争的不幸影響是它停止了通用圖靈機的開發和實現。

二戰後，英國和美國之間為了建造第一台數字計算機而進行的一場競賽已經開始并開始了。英國正在建造 ACE（自動計算引擎），美國正在建造 ENIAC（電子數值積分器和計算器）。圖靈處于 ACE 項目的外圍，而不是硬件設計的核心，因此他将思想轉向了指令表，或者我們現在所說的軟件。

标準圖靈機如圖 1所示。它由一個讀/寫磁頭和一個無限長的磁帶組成，可以一次向右或向左移動一段。讀/寫頭在磁帶上讀取和寫入符号。

圖1。

讀/寫磁頭（有時稱為控制磁頭）可以讀取、寫入或擦除其當前所在的磁帶段上的符号，但一次隻能讀取一個段。信不信由你，這種最簡單的簡單計算機能夠完成最強大的超級計算機所能做的任何事情。

如果您研究圖靈機，遲早會遇到正式符号。起初它有點吓人，但它确實有用且易于理解。有關圖靈機符号的解釋，請參見圖 2。

圖 2。

圖靈機的正式定義，表示為 M，是 M = (Q, Σ, Γ, δ, q 0 , B, F)。

含義如下：Q 是一組有限狀态，Σ (sigma) 是輸入字母表，Γ (gamma) 是磁帶字母表，δ (delta) 是轉移函數，B 是空白符号，q 0是起始狀态，F 為最終狀态。希臘字母在理論計算機科學中用作符号約定，就像它們在數學中使用一樣。

讓我們看一個示例，以便您了解圖靈機的工作原理。假設我們有一個膠帶，其中填充了符号 a 和 b，并在兩端用空白符号框起來，如圖 3所示。

圖 3。

我們将在左邊的空白處設置起始位置。這是初始狀态 q 0。我們希望圖靈機做的是将每個 a 更改為 b，将每個 b 更改為 a。我們将此圖靈機稱為符号交換器。為了對圖靈機進行編程以進行符号交換，我們需要開發一組規則或轉換函數 δ。以下是英文規則，然後翻譯成圖靈機符号： 從初始狀态 q 0開始。

如果空白在讀取頭上，則在磁帶上重新複制空白，将狀态設置為新狀态 q 1，并将讀取頭向右推進。象征性地，我們可以把它寫成 (q 0 ,B) = {q 1 , B, R}。一般來說，這意味着 (State, Symbol) = {NewState, NewSymbol, MoveTo}。使用符号，我們可以将冗長的口頭描述簡化為簡短、精确的符号聲明。這就是花時間學習和操作符号的價值。

下一步是什麼？圖靈機現在處于狀态 q 1，現在我們希望機器尋找 a 或 b 并交換它們，所以我們需要更多的轉換函數。對于狀态 q 1，如果 a 在讀取頭上，則保持狀态 q 1，在磁帶上寫入符号 b，并将頭向右推進。這轉化為 (q 1 ,a) = {q 1 , b, R}。如果 ab 在讀磁頭上方，則留在 q 1中，在磁帶上寫一個 a，然後将磁頭向右推進。這轉化為 (q 1 ,b) = {q 1 , a, R}。

為了讓機器在最終狀态 F 中停止，我們還需要一個轉換函數。如果空白符号 B 在讀取頭上方，則停止圖靈機。這轉化為 (q 1 ,B) = {F}。這個轉換函數在執行圖靈機時沒有正式定義。

為了讓圖靈機停止，必須有一個未定義的轉換，因此讀頭不能向右或向左前進。圖 4列出了描述圖靈機的所有轉換函數。我們的每個轉換都稱為一個配置。這是邊欄中調用的配置序列 什麼是計算？

圖 4。

現在我們需要運行圖靈機來看看它是否工作。在大多數經典的圖靈機文獻中，從一個轉換到另一個轉換的移動由 ( 表示。這個符号表示正在運行的圖靈機。圖 5顯示了我們的圖靈機運行時的圖形和經典表示。

為任何複雜的圖靈機使用圖形表示會變得非常麻煩并且占用大量空間，因此您幾乎看不到它們。你幾乎總是會看到經典的表示。正如您在圖 5中看到的，讀取頭由轉換函數 q 0和 q 1表示。讀頭右側的符号被認為是讀頭下方的符号。當讀頭讀取磁帶時，它會向右或向左移動并在磁帶上重新寫入符号。

圖 5。

所以我們已經證明了将符号 a 更改為符号 b 的圖靈機确實有效。那麼有什麼大不了的呢？好吧，最重要的是，将一個字符轉換為另一個字符的算法确實是一種計算，并且由于它在圖靈機上正确運行，它應該在宇宙中任何可以想象的計算機上運行！這就是圖靈機的深度。

把兩個數加起來怎麼樣？我們直觀地知道它确實是一種計算，但你如何證明呢？看看它是否在圖靈機上運行！

在磁帶上表達數字的一種方法是使用一元格式。在一元格式中，數字二表示為0110。三個一用來表示數字三，零用來分隔數字。數字五是一元格式是 0111110。我們想看看二加二是否是一個計算，所以磁帶看起來像 B0110110B（不要忘記磁帶充滿了空白，所以我們有空白符号達到無窮大膠帶的兩端）。

我們如何創建一個圖靈機來添加這兩個一元數？看錄像帶一會兒。我們想要的結果是 4，即 011110。如果我們可以将最右邊的向左移動一位，我們就會得到想要的結果。我們需要的是移位寄存器的一種形式。

圖靈機模拟現代計算機的程度令人驚訝，它是在 1936 年發明的！圖 6顯示了加法器的轉換函數，以及使用經典符号的圖靈機。通過圖靈機模拟器運行它以驗證它是如何工作的。

圖 6。

圖靈機模拟器由三部分組成：輸入磁帶文件、轉換函數文件和 tms.exe 模拟器。輸入磁帶文件是一個包含磁帶字符的 ASCII 文本文件。轉換函數文件使用類似于經典圖靈機形式的格式。注釋也可以通過在行首放置一個 C 來容納。由于經典的圖靈機表示法有點神秘，通常需要自由使用注釋（如果你想記住你做了什麼！）。一個基本的解析器從源文件中讀取轉換并将轉換加載到結構數組中。

我們真正構建的是一個解釋器。轉換函數文件是程序源代碼，輸入磁帶文件是數據，tms.exe程序是解釋器。讀取源代碼文件，将源代碼分解為單個符号或标記，然後将标記存儲在數據結構中的過程稱為解析。我們的解析器在函數 ReadTuringMachine() 中。

為了縮短代碼長度，ReadTuringMachine() 幾乎沒有錯誤檢查。這意味着轉換函數文件需要相當正确，因為 ReadTuringMachine() 不會檢測語法錯誤。

輸入磁帶符号被加載到 InputTape[MAX_TAPE_LEN] 數組中。轉換函數被加載到一個 TURING_MACHINE 結構數組中。圖 7說明了 TURING_MACHINE 結構及其與形式轉換函數的關系。

圖 7。

圖靈機模拟器可以在單步模式下運行，一次執行一個轉換，或者在自動模式下，全速執行所有轉換功能。符号交換器的輸入帶、轉換函數和計算軌迹如圖 8所示。

圖 8。

希望這篇文章能讓您了解圖靈機。這裡設計的簡單圖靈機程序隻是一個起點。

有多帶圖靈機、通用圖靈機和許多其他變體。調整 TMS 程序以讀取多個磁帶将是一個有趣的項目。

有時用圖靈機思考可能既困難又費力，但回報是獲得對計算基本性質的洞察。編寫圖靈機并看着它們在模拟器上突飛猛進是很有趣的。

嘗試設計一個圖靈機來複制字符串或進行其他基本的算術運算，例如減法或乘法。有些機器可能很容易創建，而有些機器可能非常困難。試試看。隻需創建一個輸入磁帶文件和一個轉換函數文件。

我通常在輸入磁帶文件上加上 .dat 擴展名，在轉換函數文件上加上 .tm 擴展名。沒有命名限制，所以如果你願意，可以使用你自己的系統。

想了解更多？有很多網站包含有關圖靈機的詳細、有趣的信息，以及您可以找到通過模拟器運行的大量轉換函數。

請記住，在所有科學中，計算機科學仍處于起步階段。有許多重要的發現有待作出，也有許多重大的問題有待解決。

偉大的發現是從第一原理的框架中産生的。使用第一原理設備，例如圖靈機，可能會有所幫助。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!