算法和數據結構如何與圖靈機相關？

Question

我的The Design and Analysis of Computer Algorithms已於今天到貨。在第一章中，作者介紹了圖靈機。我有兩個其他算法教科書，Introduction to Algorithms和The Algorithm Design Manual，但他們都沒有談論圖靈機，儘管他們在算法和數據結構方面很有名。

我想了解什麼是圖靈機，算法/數據結構網絡化之間的關係。理解圖靈機成爲算法專家真的很重要嗎？

Answer 1

的原因，圖靈機描述數據結構和算法的時候是很重要的是，他們提供了一個數學模型中，我們可以描述的算法是什麼。大多數時候，算法都是使用高級語言或僞代碼來描述的。例如，我可以描述的算法在一個這樣的數組找到最大值：

Set max = -infinity 
For each element in the array: 
    If that element is greater than max: 
     Set max equal to that element. 

從這些描述中可以很容易地看到算法如何工作的，它會很容易把它翻譯成源代碼。但是，假設我寫出了這樣的描述：

Guess the index at which the maximum element occurs. 
Output the element at that position. 

這是一個有效的算法嗎？也就是說，我們可以說「猜索引」並嚴格定義它的含義嗎？如果我們允許這樣做，那麼需要多長時間才能做到這一點？如果我們不允許，爲什麼不呢？第一個描述與第二個描述有什麼不同？

爲了有一個算法的數學嚴格的定義，我們需要有一臺計算機是如何工作的一些形式化模型和所能做和不能做什麼。圖靈機是正式定義計算的一個常用的方法，儘管有其他人可以被使用（register machines，串改寫系統，教會的lambda calculus等），一旦我們定義計算的數學模型，我們就可以開始談論什麼樣的算法描述是有效的 - 即那些可以用我們的計算模型實現的算法描述。

很多現代的算法，關鍵取決於計算的基本模型的屬性。例如，cache-oblivious algorithms假定計算模型有一些未知大小的內存緩衝區和一個雙層內存。一些算法要求底層機器是transdichotomous，這意味着機器字的大小必須至少足夠大以容納任何問題的大小。隨機算法需要randomess的正式定義以及機器如何使用隨機值。非確定性算法需要一種指定非確定性計算的方法。基於電路的算法必須知道什麼電路原語是和不被允許的。量子計算機需要一個關於哪些操作是不允許的正式定義，以及給定算法的定義是什麼，以便輸出是概率性的。分佈式算法需要機器間通信的正式定義。

簡而言之，在描述算法時，明確什麼是和不允許是很重要的。然而，要成爲一名優秀的程序員或者對算法有着紮實的把握，你不需要內部和外部必須知道圖靈機，也不需要知道如何使用它們來編碼特定問題的具體細節。但是，您應該知道的是計算模型可以做什麼以及不可以做什麼，以及每次操作的成本是多少。這樣，您就可以推斷算法的有效性，它們使用的各種資源（時間，空間，內存，通信，隨機數，不確定性等）的數量。但是那就是說，如果你不瞭解底層模型，就不要驚慌。

還有一個原因需要考慮計算的基本模型 - 討論它的侷限性。每種計算模型都有其侷限性，並且在某些情況下，您可以證明某些算法不可能存在某些問題，或者任何解決某些問題的算法都必須使用一定數量的給定資源。在算法設計中出現的最常見的例子是NP硬度的概念。有人猜想某些問題是非常「困難」的解決，但是這種困難的正式定義依賴於圖靈機和非確定性圖靈機的知識。理解模型在這種情況下很有用，因爲它可以讓你推理某些問題的計算可行性。

希望這會有所幫助！

Answer 2

圖靈機只是分析計算的理論工具，我們可以通過創建計算它的圖靈機來指定算法。它們在可計算性研究中非常有用，也就是說，如果完全有可能計算一個函數。 Hopchroft和Ullmann在傳統的book中討論了圖靈機和其他幾種正式的語言結構。在討論NP完整性時，圖靈機也出現在例如Garey和Johnson的書this中。

這兩本書和一般的圖靈機是相當的理論。如果你對學術有興趣，我會推薦他們。然而，如果你想對實際計算機上實現的算法有一個實際的理解，並在真實數據上運行，那麼我認爲只有對圖靈機有一個粗略的理解纔是重要的。