“活”過來的經(jīng)典計算機——圖靈機

陳凱

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

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

由上圖可以看出，圖靈機構(gòu)造很簡單，由一條紙帶、一個指向紙帶的讀寫頭構(gòu)成。“Load”窗口用于設(shè)置紙帶上原始的數(shù)據(jù)。

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

活動表情包

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