“活”過來的經典計算機——圖靈機

陳凱

圖靈機是一個數學模型，這個模型很有用。例如，人們可以借助圖靈機證明世界上存在的某些問題，是不可能被任何有步驟的、確定性的算法解決的。又如，人們可以借助圖靈機證明，在不改變機械結構的前提下，讓機器做不同的運算。但除了狂熱的電子發燒友，世界上并沒有多少人真正利用圖靈機來解決工作中的實際問題，不過，或許可以把圖靈機當成一臺考驗智力的游戲機，不同的任務就像一道道游戲關卡，通關之后，便會對圖靈機的深刻內涵有所領悟。

如果在搜索引擎中搜索“turing machine simulator”，可以找到許多不同的圖靈機模擬器，本文以https：//turingmachinesimulator.com網站提供的圖靈機模擬器為例（如下圖），邊玩邊學，看看圖靈機是怎么工作的。

由上圖可以看出，圖靈機構造很簡單，由一條紙帶、一個指向紙帶的讀寫頭構成?！癓oad”窗口用于設置紙帶上原始的數據。

程序運行的原理很容易理解，讀寫頭只要讀到“0”，就往右移動，并且機器狀態總是在q0和q1兩者間發生變化，最后若變回q0，則說明讀了偶數次“0”。如果讀寫頭讀到的數字和寫的數字一樣，其實就是保持紙帶數據不變。如果讀寫頭更改紙帶上的數據，便會使紙帶和讀寫頭的變化更復雜。

活動表情包

有了上面的基礎，就可以編寫出一些好玩的程序。：-）是一張瞇著眼睛的笑臉，8-（是一張瞪大眼睛憤怒的臉，可以借助圖靈機讓兩張臉快速切換，程序如下。圖靈大概沒想到他的模型還能產生動畫片的效果。