AI數學基礎之:确定圖靈機和非确定圖靈機

簡介

圖靈機是由艾倫·麥席森·圖靈在1936年描述的一種抽象機器，它是人們使用紙筆進行數學運算的過程的抽象，它肯定了計算機實作的可能性，并給出了計算機應有的主要架構，引入了讀寫與算法與程式語言的概念為現代計算機的發明打下了基礎。

本文将會講解一下圖靈機中的兩種類型：确定圖靈機和非确定圖靈機。

圖靈機

圖靈機是一種數學計算模型，它定義了一個抽象機器，該抽象機器根據規則表來操縱帶子上的符号。盡管該模型很簡單，但是在任何給定計算機算法的情況下，都可以建構出模拟該算法邏輯的圖靈機。

簡單點說，圖靈機就是一個模拟算法運作的抽象機器。它是這樣定義的：

1. 有一個無限長度的錄音帶，這個錄音帶被分成了一個接一個的單元格，錄音帶被用于寫入字母和符号。
2. 一個讀寫錄音帶的磁頭，這個磁頭負責控制堆錄音帶的寫入和左右移動。
3. 一個狀态寄存器，用來存儲圖靈機的狀态。
4. 一個指令表，可以根據機器目前所處的狀态和錄音帶上目前的符号，訓示機器進行特定的操作。比如：擦除或者寫入一個符号、向左或者向右移動磁頭。

可以看到整個圖靈機基本上模拟了程式的執行步驟。

圖靈機雖然可以表示任意的計算程式，但是因為其極其簡單的設計實際上并不适合進行計算，是以現實世界的現代計算機都是對圖靈機的優化設計。

圖靈完備性是指指令系統模拟圖靈機的能力。從理論上講，圖靈完整的一種程式設計語言可以表達計算機可以完成的所有任務。如果忽略有限記憶體的限制，幾乎所有程式設計語言都是圖靈完備的。

圖靈機的缺點

雖然圖靈機可以表示任何計算任務，但是圖靈機太過于簡單了，在某些複雜的模型中無法很好的進行使用。比如在現代計算機中的RASP随機存儲模型，因為RASP可以在寄存器中引用其他的寄存器，是以可以基于記憶體索引進行優化，這種優化是在圖靈機中無法實作的。

圖靈機的另一個限制是它們不能很好地進行并發模組化。另外，因為在早期的時候，計算機的使用通常僅限于批處理，即非互動式任務，每個任務都從給定的輸入資料中産生輸出資料。 是以圖靈機在描述現代互動式應用也有一些限制。

等效圖靈機

因為圖靈機是一種假想的裝置，它為計算機算法的概念提供了理論基礎。并且因為圖靈機模型比較簡單，對于複雜問題的描述比較弱，是以出現了很多圖靈機的等效模型，雖然這些模型并不一定比圖靈機強大，但是這些模型是真正存在的，并且使用他們可以更加容易的解決特定問題。

确定圖靈機

在确定性圖靈機（DTM）中，其控制規則規定了在任何給定情況下最多隻能執行一個動作。

确定性圖靈機具有轉換功能，對于錄音帶頭下的給定狀态和符号，該轉換功能指定了三件事：

要寫入錄音帶的符号，頭部應移動的方向（向左，向右或都不向），以及有限控制的後續狀态。

例如，狀态3的錄音帶上的X可能會使DTM在錄音帶上寫Y，将磁頭向右移動一個位置，然後切換到狀态5。

非确定圖靈機

在理論計算機科學中，非确定性圖靈機（NTM）是一種理論計算模型，其控制規則在某些給定情況下指定了多個可能的動作。 也就是說，NTM的下一個狀态不是完全由其動作和它所看到的目前符号決定的（不同于确定性圖靈機）。

例如，狀态3的錄音帶上的X可能允許NTM：

輸入Y，向右移動，然後切換到狀态5或者寫一個X，向左移動，并停留在狀态3。

那麼問題來了，對于非确定圖靈機來說是怎麼進行下一步的選擇的呢？實際上NTM足夠幸運，它總是會選擇那個能夠最終指向接受狀态的那一步。

你可以把NTM的諸多分支看成是許多副本，每個副本遵循一個可能的轉換。 DTM遵循的是單個“計算路徑”，而NTM則是“計算樹”。 如果樹中至少有一個分支導緻接受狀态，那麼NTM就會接受這個輸入狀态。

我們看下兩者的決策圖：

确定圖靈機和非确定圖靈機 兩者在計算上是等效的，也就是說，盡管它們通常具有不同的運作時，但可以将任何NDTM轉換為DTM（反之亦然）。 這可以通過構造來證明。

本文已收錄于 http://www.flydean.com/03-turing-machine/

最通俗的解讀，最深刻的幹貨，最簡潔的教程，衆多你不知道的小技巧等你來發現！

歡迎關注我的公衆号:「程式那些事」,懂技術，更懂你！