這篇文章主要介紹“什么是確定圖靈機和非確定圖靈機”，在日常操作中，相信很多人在什么是確定圖靈機和非確定圖靈機問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”什么是確定圖靈機和非確定圖靈機”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
圖靈機是一種數學計算模型，它定義了一個抽象機器，該抽象機器根據規則表來操縱帶子上的符號。盡管該模型很簡單，但是在任何給定計算機算法的情況下，都可以構建出模擬該算法邏輯的圖靈機。
簡單點說，圖靈機就是一個模擬算法運行的抽象機器。它是這樣定義的：
有一個無限長度的磁帶，這個磁帶被分成了一個接一個的單元格，磁帶被用于寫入字母和符號。
一個讀寫磁帶的磁頭，這個磁頭負責控制堆磁帶的寫入和左右移動。
一個狀態寄存器，用來存儲圖靈機的狀態。
一個指令表，可以根據機器當前所處的狀態和磁帶上當前的符號，指示機器進行特定的操作。比如：擦除或者寫入一個符號、向左或者向右移動磁頭。
可以看到整個圖靈機基本上模擬了程序的執行步驟。
圖靈機雖然可以表示任意的計算程序，但是因為其極其簡單的設計實際上并不適合進行計算，所以現實世界的現代計算機都是對圖靈機的優化設計。
圖靈完備性是指指令系統模擬圖靈機的能力。從理論上講，圖靈完整的一種編程語言可以表達計算機可以完成的所有任務。如果忽略有限內存的限制，幾乎所有編程語言都是圖靈完備的。
雖然圖靈機可以表示任何計算任務，但是圖靈機太過于簡單了，在某些復雜的模型中無法很好的進行使用。比如在現代計算機中的RASP隨機存儲模型，因為RASP可以在寄存器中引用其他的寄存器，所以可以基于內存索引進行優化，這種優化是在圖靈機中無法實現的。
圖靈機的另一個限制是它們不能很好地進行并發建模。另外，因為在早期的時候，計算機的使用通常僅限于批處理，即非交互式任務，每個任務都從給定的輸入數據中產生輸出數據。 所以圖靈機在描述現代交互式應用也有一些限制。
因為圖靈機是一種假想的設備，它為計算機算法的概念提供了理論基礎。并且因為圖靈機模型比較簡單，對于復雜問題的描述比較弱，所以出現了很多圖靈機的等效模型，雖然這些模型并不一定比圖靈機強大，但是這些模型是真正存在的，并且使用他們可以更加容易的解決特定問題。
在確定性圖靈機（DTM）中，其控制規則規定了在任何給定情況下最多只能執行一個動作。
確定性圖靈機具有轉換功能，對于磁帶頭下的給定狀態和符號，該轉換功能指定了三件事：
要寫入磁帶的符號，頭部應移動的方向（向左，向右或都不向），以及有限控制的后續狀態。
例如，狀態3的磁帶上的X可能會使DTM在磁帶上寫Y，將磁頭向右移動一個位置，然后切換到狀態5。
在理論計算機科學中，非確定性圖靈機（NTM）是一種理論計算模型，其控制規則在某些給定情況下指定了多個可能的動作。 也就是說，NTM的下一個狀態不是完全由其動作和它所看到的當前符號決定的（不同于確定性圖靈機）。
例如，狀態3的磁帶上的X可能允許NTM：
輸入Y，向右移動，然后切換到狀態5或者寫一個X，向左移動，并停留在狀態3。
那么問題來了，對于非確定圖靈機來說是怎么進行下一步的選擇的呢？實際上NTM足夠幸運，它總是會選擇那個能夠最終指向接受狀態的那一步。
你可以把NTM的諸多分支看成是許多副本，每個副本遵循一個可能的轉換。 DTM遵循的是單個“計算路徑”，而NTM則是“計算樹”。 如果樹中至少有一個分支導致接受狀態，那么NTM就會接受這個輸入狀態。
我們看下兩者的決策圖：
確定圖靈機和非確定圖靈機 兩者在計算上是等效的，也就是說，盡管它們通常具有不同的運行時，但可以將任何NDTM轉換為DTM（反之亦然）。 這可以通過構造來證明。
到此，關于“什么是確定圖靈機和非確定圖靈機”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
