圖靈機是一個真正的設備還是虛構的概念？

Question

當我在研究圖靈機和PDA時，我在想第一臺計算機是圖靈機。

因此，我認爲存在一個稱爲圖靈機的實用機器，它的狀態可以用一些特殊的設備來表示（比如觸發器），它可以接受磁帶上的輸入。因此我問懷疑How input string is represented in magnetic tapes?。但是通過我的書中的答案和細節，我開始知道圖靈機是一些假設的東西。

我的問題是，圖靈機如何實際應用？例如，它如何用於檢查當前處理器中的拼寫錯誤。

圖靈機過時了嗎？還是仍在使用？

Answer 1

實踐中沒有使用圖靈機有幾個原因。對於初學者來說，不可能構建一個，因爲你需要無限的資源來構建無限大的磁帶。而且，由於數據訪問的順序性，圖靈機本質上比其他計算模型慢。例如，圖靈機不能先跳過陣列的中間位置，而不先跳過它想要跳過的所有陣列元素。最重要的是，圖靈機非常難以設計。例如，嘗試編寫一個圖靈機來對32位整數列表進行排序。 （其實請不要，這真的很難！）

這就引出了問題......爲什麼要研究圖靈機呢？幸運的是，有很多原因可以做到這一點：

1. 推理什麼可能被計算的限制。因爲圖靈機能夠模擬行星地球上的任何計算機（或根據Church-Turing論文，任何物理上可實現的計算設備），如果我們能夠顯示圖靈機可以計算的極限，我們可以證明什麼希望能夠在實際的計算機上完成。

2. 正式確定算法的定義。爲什麼二進制搜索算法，而聲明「猜答案」不是？爲了回答這個問題，我們必須有一個計算機是什麼和算法是什麼的正式模型。將圖靈機作爲計算模型使我們能夠嚴格定義算法是什麼。實際上沒有人想要將算法轉換爲格式，但是這樣做的能力使算法和可計算性理論領域具有堅實的數學基礎。

3. 確定性和非確定性算法的定義。現在計算機科學中最大的問題可能就是P = NP的問題。如果你對P和NP有一個正式的定義，這個問題纔有意義，而如果是確定性和非確定性計算（雖然在技術上它們可以用二階邏輯來定義），這些問題反過來需要定義。使用圖靈機讓我們可以談論NP中的重要問題，併爲我們提供一種找到NP完全問題的方法。例如，SAT是NP-complete的證明使用SAT可用於編碼圖靈機並且它是在輸入上執行的事實。

希望這有助於！

Answer 2

這是一個不能實現的概念設備（由於無限磁帶的要求）。有些人已經構建了圖靈機的物理實現，但由於物理限制，它不是真正的圖靈機。

這裏的一個的視頻：http://www.youtube.com/watch?v=E3keLeMwfHY

Answer 3

這是一個理論機，

圖靈機是根據一個表，操縱在磁帶上的帶符號的理論設備維基百科

以下段落的規則。儘管它很簡單，但圖靈機可以適用於模擬任何計算機算法的邏輯，並且特別適用於解釋計算機內部CPU的功能。 塊引用

本機與其他機器等非確定性機器（在實際不存在）沿是在計算複雜性是非常有用的，並證明一個算法是比另一個更硬或一個算法是不可解..例如

Answer 4

圖靈機並不完全是物理機器，而是他們基本上是概念機器。圖靈的概念是假設，這在現實世界中很難實現，因爲我們需要無限的磁帶來實現小而簡單的解決方案。