圖靈機演算法

❶ 用圖靈機描述計算機復雜度，其含義是圖靈機演算法的復雜度還是判斷圖靈機的演算法的復雜度

圖靈機程序的復雜度是由外部的輸入和輸出來決定圖靈機內部的演算法需要的時間和空間的復雜度。圖靈機的時間復雜性T(n)是它處理所有長度為n的輸入所需要的最大計算步數。如果對於某個長度為n的輸入，圖靈機不停機，則T(n)對這個值無定義。圖靈機的空間復雜性S（n）是它處理所有長度為n的輸入時，在k帶上所使用過的方格數的總和。如果某個讀寫頭無限的向右移動而不停機，s(n)也無定義。

❷ 什麼是圖靈機和圖靈測試

阿蘭·麥席森·圖靈（Alan Mathison Turing，1912.6.23—1954.6.7），英國數學家、邏輯學家，被稱為人工智慧之父。 1931年圖靈進入劍橋大學國王學院，畢業後到美國普林斯頓大學攻讀博士學位，二戰爆發後回到劍橋，後曾協助軍方破解德國的著名密碼系統Enigma，幫助盟軍取得了二戰的勝利。 阿蘭·麥席森·圖靈，1912年生於英國倫敦，1954年死於英國的曼徹斯特，他是計算機邏輯的奠基者，許多人工智慧的重要方法也源自於這位偉大的科學家。他對計算機的重要貢獻在於他提出的有限狀態自動機也就是圖靈機的概念，對於人工智慧，它提出了重要的衡量標准「圖靈測試」，如果有機器能夠通過圖靈測試，那他就是一個完全意義上的智能機，和人沒有區別了。他傑出的貢獻使他成為計算機界的第一人，現在人們為了紀念這位偉大的科學家將計算機界的最高獎定名為「圖靈獎」。上中學時，他在科學方面的才能就已經顯示出來，這種才能僅僅限於非文科的學科上，他的導師希望這位聰明的孩子也能夠在歷史和文學上有所成就，但是都沒有太大的建樹。少年圖靈感興趣的是數學等學科。在加拿大他開始了他的職業數學生涯，在大學期間這位學生似乎對前人現成的理論並不感興趣，什麼東西都要自己來一次。大學畢業後，他前往美國普林斯頓大學也正是在那裡，他製造出了以後稱之為圖靈機的東西。圖靈機被公認為現代計算機的原型，這台機器可以讀入一系列的零和一，這些數字代表了解決某一問題所需要的步驟，按這個步驟走下去，就可以解決某一特定的問題。這種觀念在當時是具有革命性意義的，因為即使在50年代的時候，大部分的計算機還只能解決某一特定問題，不是通用的，而圖靈機從理論上卻是通用機。在圖靈看來，這台機器只用保留一些最簡單的指令，一個復雜的工作只用把它分解為這幾個最簡單的操作就可以實現了，在當時他能夠具有這樣的思想確實是很了不起的。他相信有一個演算法可以解決大部分問題，而困難的部分則是如何確定最簡單的指令集，怎麼樣的指令集才是最少的，而且又能頂用，還有一個難點是如何將復雜問題分解為這些指令的問題。 1936年，圖靈向倫敦權威的數學雜志投了一篇論文，題為「論數字計算在決斷難題中的應用」。在這篇開創性的論文中，圖靈給「可計算性」下了一個嚴格的數學定義，並提出著名的「圖靈機」(Turing Machine)的設想。「圖靈機」不是一種具體的機器，而是一種思想模型，可製造一種十分簡單但運算能力極強的計算裝置，用來計算所有能想像得到的可計算函數。「圖靈機」與「馮·諾伊曼機」齊名，被永遠載入計算機的發展史中。1950年10月，圖靈又發表了另一篇題為「機器能思考嗎」的論文，成為劃時代之作。也正是這篇文章，為圖靈贏得了「人工智慧之父」的桂冠。

❸ 圖靈機的工作原理

普適圖靈機的概念。雖然其細節是復雜的，但是它背後的原則並不十分復雜。它的基本思想是把任意一台圖靈機T的指令的表編碼成在磁帶上表示成0和1的串。然後這段磁帶被當作某一台特殊的被稱作普適圖靈機U的輸入的開始部分，接著這台機器正如T所要進行的那樣，作用於輸入的餘下部分。普適圖靈機是萬有的模仿者。「磁帶」的開始部分賦予該普適機器U需要用以准確模擬任何給定機器T的全部信息！

為了了解這是如何進行的，我們首先需要一種給圖靈機編號的系統方式。考慮定義某個特殊的，譬如講在前面描述的圖靈機的一個指令表。我們必須按照某種准確的方案把這表編碼成0和1的串。我們可藉助於以前採用的「收縮」步驟來辦到。因為，如果我們用數2，3，4，5和6來分別代表符號R、L、STOP、箭頭（→）以及逗點，那麼我們就可以用110、1110、11110、111110以及1111110的收縮把它們編碼。這樣，出現在該表中的這些符號實際的串可以採用分別被編碼成0和10的位數0和1。由於在該圖靈機的表中，在二進位計數的結尾大寫的數的位置足以把大寫的0和1從其他小寫的阿拉伯數字中區分開來，所以我們不需要用不同的記號。這樣，1101將被讀成二進位數1101，而在磁帶上被編碼成1010010。特別是，00讀作00，它可毫不含糊地被編碼成0，或者作為被完全省略的符號。實際上我們可以不必對任何箭頭或任何在它緊前頭的符號進行編碼，而依靠指令的數字順序去標明哪些符號必須是什麼。盡管在採用這個步驟時，在必要之處要提供一些額外的「啞」指令，以保證在這個順序中沒有縫隙。這樣的做法具有相當好的經濟性。（例如，圖靈機XN+1沒有告訴我們對1100要做什麼的命令，這是因為這條指令在機器運行時從不發生，所以我們應該插入一條「啞」指令，譬如講1100→00R，它可合並到表中而不改變任何東西。類似地，我們應該把101→00R插入到XN×2中去。）若沒有這些「啞的」，表中後面的指令的編碼就會被糟蹋了。因為在結尾處的符號L或R足以把一條指令和另一條隔開，所以我們在每一指令中實際不需要逗號。因此，我們採用下面的編碼：

0表示0或0，10表示1或1，110表示R，1110表示L，11110表示stop。

作為一個例子，讓我們為圖靈機XN+1編碼（插入指令1100→00R）。在去掉箭頭和在它們緊前面的位數以及逗號之後，我們得到

00R 11R 00R 101R 110L 101R 01STOP

1000L 1011L 1001L1100R101R00R1111R

111R 1110R

為了和早先說的相一致，我們可以去掉每一個00，並把每一個01簡單地用1來取代，這樣得到



001L1100R101RR1111R111R1110R

如下是在磁帶上的相應的碼：



我們總是可以把開始的110（以及它之前的無限的空白磁帶）刪去。由於它表示00R，這代表開頭的指令00→00R。而我已隱含地把它當作所有圖靈機共有的。這樣儀器可從磁帶記號左邊任意遠的地方向右跑到第一個記號為止。而且，由於所有圖靈機都應該把它們的描述用最後的110結束（因為它們所有都用R、L或STOP來結束），所以我們也可把它（以及假想跟在後面的0的無限序列）刪去。這可以算作兩個小節約。所得到的二進位數是該圖靈機的號碼，它在XN+1的情況下為：

。
這一特殊的數在標准十進位記號下為

。

我們有時不嚴格地把號碼為n的圖靈機稱為第n台圖靈機，並用Tn來表示。這樣，XN+1是第台圖靈機！

我們必須順著這圖靈機的「表」走這么遠，才找到一台甚至只進行如此平凡的（在擴展二進位記號上）對自然數加一的運算，這真使人印象深刻！（盡管在我的編碼中還可以有很少的改善餘地，但我認為自己進行得相當有效率。）實際存在某些更低號碼的有趣的圖靈機。例如，UN+1的二進位號碼為

101011010111101010

它只是十進位制的177642！這樣，只不過是把一個附加的1加到序列1的尾巴上的特別平凡的圖靈機UN+1是第177642台圖靈機。為了好奇的原因，我們可以注意在任一種進位制中「乘二」是在圖靈機表中這兩個號碼之間的某處。我們找到XN×2的號碼為10389728107，而UN×2的號碼為1492923420919872026917547669。

人們從這些號碼的大小，也許會毫不奇怪地發現，絕大多數的自然數根本不是可工作的圖靈機的號碼。現在我們根據這種編號把最先的十三台圖靈機列出來：

T0：00→00R，01→00R，

T1：00→00R，01→00L，

T2：00→00R，01→01R，

T3：00→00R，01→00STOP，

T4：00→00R，01→10R，

T5：00→00R，01→01L，

T6：00→00R，01→00R，10→00R，

T7：00→00R，01→？？？，

T8：00→00R，01→100R，

T9：00→00R，01→10L，

T10：00→00R，01→11R，

T11：00→00R，01→01STOP，

T12：00→00R，01→00R，10→00R。

其中，T0簡單地就是向右移動並且抹去它所遇到的每一件東西，永不停止並永不往回退。機器T1最終得到同樣的效應。但它是以更笨拙的方法，在它抹去磁帶上的每個記號後再往後跳回。機器T2也和機器T0一樣無限地向右移動，但是它更有禮貌，簡單地讓磁帶上的每一件東西原封不動。由於它們中沒有一台會停下，所以沒有一台可以合格地被稱為圖靈機。T3是第一台可敬的機器。它的確是在改變第一個（最左邊）的1為0後便謙虛地停止。

T4遭遇了嚴重的問題。它在磁帶上找到第一個1後就進入了一個沒有列表的內態，所以它沒有下一步要做什麼的指令。T8、T9和T10遇到同樣的問題。T7的困難甚至更基本。把它編碼的0和1的串涉及到五個接續的1的序列：110111110。對於這種序列不存在任何解釋，所以只要它在磁帶上發現第一個1就被絆住。（我把T7或其他任何機器Tn，它的n的二進位展開包含多於四個1的序列稱為不是正確指明的。）機器T5、T6和T12遭遇到和T0、T1和T2類似的問題。它們簡單地、無限地、永遠不停地跑下去。所有T0、T1、T2、T4、T5、T6、T7、78、T9、T10和T12都是偽品！只有T3和T11是可工作的，但不是非常有趣的圖靈機。T11甚至比T3更謙虛，它在第一次遇到1時就停止，並且沒有改變任何東西！

我們應該注意到，在表中還有一個多餘。由於T6和T12從未進入內態1，機器T12和T6等同，並在行為上和T0等同。我們既不必為這個多餘，也不必為表中的圖靈機偽品而煩惱。人們的確可以改善編碼以擺脫許多偽品和大大減少重復。所有這些都是以使我們可憐的普適圖靈機變得更復雜作為代價。普適圖靈機必須把所讀到的號碼n解碼並假裝成圖靈機Tn。如果我們可以把所有偽品（或者多餘量）取走，這還是值得做的。但是，我們很快就會看到，這是不可能的！這樣，我們就不觸動我們的編碼好了。

例如，可方便地把具有

…0001101110010000…

接續記號的磁帶解釋成某個數字的二進位表示。我們記得0在兩端會無限地繼續下去，但是只有有限個1。我還假定1的數目為非零（也就是說至少有一個1）。我們可以選擇去讀在第一個和最後一個1（包括在內）之中的有限的符號串，在上述的情況是為一自然數的二進位寫法
110111001，

它在十進位表示中為441。然而，這一過程只能給我們奇數（其二進位表示以1結尾的數）。而我們要能表示所有的自然數。這樣，我們採取移走最後的1的簡單方案（這個1僅僅被當作表示這一程序的終止記號），而把餘下來的當成二進位數來讀5。因此，對於上述的例子，我們有二進位數

11011100，

它是十進位的220。這個步驟具有零也用磁帶上的記號代表的好處，也就是

…0000001000000…

我們考慮圖靈機Tn對我們從右邊提供給它的磁帶上（有限的）0和1的串的作用。根據上面給出的方案，可方便地把這串也考慮作某一個數，譬如m的二進位代表。我們假定，機器Tn在進行了一系列的步驟後最終到達停止（即到達STOP）。現在機器在左邊產生的二進位數串是該計算的答案。讓我們也以同樣方式把這當作，譬如是p的二進位代表來讀。我們把表達當第n台圖靈機作用到m上時產生p的關系寫成：

Tn(m)=p。

現在，以稍微不同的方式看這一關系。我們把它認為是一種應用於一對數n和m以得到數p的一個特別運算。（這樣，若給定兩個數n和m，視第n台圖靈機對m作用的結果而得出p。）這一特別運算是一個完全演算法的步驟。所以它可由一台特殊的圖靈機U來執行。也就是說，U作用到一對(n，m)上產生p。由於機器U必須作用於n和m兩者以產生單獨結果p，我們需要某種把一對(n，m)編碼到一條磁帶上的方法。為此，我們可假定n以通常二進位記號寫出並緊接著以序列111110終結。（我們記得，任一台正確指明的圖靈機的二進位數都是僅僅由0，10，110，1110和11110組成的序列，因此它不包含比四個1更多的序列。這樣，如果Tn是正確指明的機器，則111110的發生的確表明數n的描述已終結。）按照我們上面的規定，跟著它的每一件東西簡單地是代表m的磁帶（也就是，緊跟二進位數m的是1000…）。這樣，這第二個部分簡單地就是Tn假設要作用的磁帶。

作為一個例子，如果我們取n=11和m=6當作U要作用的磁帶，其記號序列為

…000101111111011010000…

這是由以下組成的：

…0000（開始的空白帶）

1011（11的二進位表示）

111110（終結n）

110…（6的二進位表示）

10000…（餘下的磁帶）。

在Tn作用到m上的運算的每一接續的步驟，圖靈機U要做的是去考察n的表達式中的接續數位的結構，以使得在m的數位（也就是Tn的磁帶）上可進行適當的代換。在原則上（雖然在實踐中肯定很繁瑣）不難看到人們實際如何建造這樣的一台機器。它本身的指令表會簡單地提供一種，在每一階段讀到被編碼到數n中的「表」中，應用到m給出的磁帶的位數時，合適元素的手段。肯定在m和n的數位之間要有許多前前後後的進退，其過程會極為緩慢。盡管如此，一定能提供出這台機器的指令表，而我們把它稱為普適圖靈機。把該機器對一對數n和m的作用表為U(n,m)，我們得到：

U(n,m)=Tn(m)。

這兒Tn是一台正確指明的圖靈機6。當首先為U提供數n時，它准確地摸擬第n台圖靈機！

因為U為一台圖靈機，它自身也必須有一號碼；也就是說，我們有

U=Tu

此處號碼u待定。u究竟是多少呢？事實上我們可以准確地給出u=

❹ 什麼是圖靈機

圖靈機

1936年，阿蘭·圖靈提出了一種抽象的計算模型 —— 圖靈機 (Turing Machine)。圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：

在紙上寫上或擦除某個符號；

把注意力從紙的一個位置移動到另一個位置；

而在每個階段，人要決定下一步的動作，依賴於 (a) 此人當前所關注的紙上某個位置的符號和(b) 此人當前思維的狀態。為了模擬人的這種運算過程，圖靈構造出一台假想的機器，該機器由以下幾個部分組成：

一條無限長的紙帶。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號 表示空白。紙帶上的格子從左到右依此被編號為 0, 1, 2, ... ，紙帶的右端可以無限伸展。

一個讀寫頭。該讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，並能改變當前格子上的符號。

一個狀態寄存器。它用來保存圖靈機當前所處的狀態。圖靈機的所有可能狀態的數目是有限的，並且有一個特殊的狀態，稱為停機狀態。

一套控制規則。它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，並改變狀態寄存器的值，令機器進入一個新的狀態。

注意這個機器的每一部分都是有限的，但它有一個潛在的無限長的紙帶，因此這種機器只是一個理想的設備。圖靈認為這樣的一台機器就能模擬人類所能進行的任何計算過程

自動機
automata

對信號序列進行邏輯處理的裝置。在自動控制領域內，是指離散數字系統的動態數學模型，可定義為一種邏輯結構，一種演算法或一種符號串變換。自動機這一術語也廣泛出現在許多其他相關的學科中，分別有不同的內容和研究目標。在計算機科學中自動機用作計算機和計算過程的動態數學模型，用來研究計算機的體系結構、邏輯操作、程序設計乃至計算復雜性理論。在語言學中則把自動機作為語言識別器，用來研究各種形式語言。在神經生理學中把自動機定義為神經網路的動態模型，用來研究神經生理活動和思維規律，探索人腦的機制。在生物學中有人把自動機作為生命體的生長發育模型，研究新陳代謝和遺傳變異。在數學中則用自動機定義可計算函數，研究各種演算法。現代自動機的一個重要特點是能與外界交換信息，並根據交換得來的信息改變自己的動作，即改變自己的功能，甚至改變自己的結構，以適應外界的變化。也就是說在一定程度上具有類似於生命有機體那樣的適應環境變化的能力。
自動機與一般機器的重要區別在於自動機具有固定的內在狀態，即具有記憶能力和識別判斷能力或決策能力，這正是現代信息處理系統的共同特點。因此，自動機適宜於作為信息處理系統乃至一切信息系統的數學模型。自動機可按其變數集和函數的特性分類，也可按其抽象結構和聯結方式分類。主要有：有限自動機和無限自動機、線性自動機和非線性自動機、確定型自動機和不確定型自動機、同步自動機和非同步自動機、級聯自動機和細胞自動機等。
參考資料：http://www.swarmagents.com/javaclass/ca.htm

❺ 圖靈機是什麼東西啊

其實呢，圖靈機的來歷忒單純。以前一個叫圖靈的閑人養了只無所事事的小母雞。圖靈成天忙著跑馬拉松，懶得照顧它，就裝了條在雞看來無限長分格的傳送帶，定時傳送食物和水。而雞閑來無聊，便走來走去，在帶子上擺放物事，權作耍子。郁悶時在格子里放根樹枝。興奮了在某個格子里下個蛋。想起了還可以把蛋換成樹枝，或者把樹枝換成蛋。不高興了在傳送帶上扔顆石頭，於是傳送帶就卡住了。某天小母雞不小心把一株野生大麻當雞骨草吞了，high得不行，繞著傳送帶發瘋：
在傳送帶靠左的地方放下一根樹枝一個蛋：10
在傳送帶靠右的地方放下兩根樹枝：11
回到左邊，把樹枝揀起來，再把蛋換成樹枝：1
回到右邊，把兩根樹枝換成一根樹枝兩個蛋：100
回到左邊，把樹枝揀起來
回到右邊，把最右邊的蛋換成樹枝：101
這下左邊的樹枝和蛋都沒了。小母雞意興索然，一怒之下扔顆石頭卡死機器。

剛從雜貨店提了袋蘋果的圖靈路過，目睹這一切。不由靈光一現：這不2+3=5么？原來加法還可以這么玩兒啊！以後不用為算帳發愁了。不過圖靈的興趣不在算帳，而在玩兒tic-tac-toe。問題是小母雞智力有限。要她理解tic-tac-toe這樣的東東還不如讓公牛上樹兔子下蛋。幸好圖靈是個好琢磨的勤快人，沒事喜歡讀一個叫Kurt Godel的德國人的文章。而Godel崇拜一個叫David Hilbert的老鄉。Hilbert在德國哥廷根討生活時沒事喜歡玄想，一不小心在世紀之交提出23個問題。居然引得此後100年來無數閑人神魂顛倒。Godel對第10個問題著了迷。研究幾年後，寫了篇帖子總結心得，順便告訴大家，Hilbert也有猜錯的時候。第10個問題的答案是我們不能依靠形式化方法找到所有丟番都方程的解。而推論就是大家就不用指望設立幾個事實（閑人們管這叫公理），再用一套規則推出所有真理。「我們必須知道，我們必將知道」的難度比Hilbert預計的大多了。這一下徹底broke Hilbert』s heart。不過我跑題了。Godel的論文花了大量篇幅描述怎麼用數字來表示自然數以外更復雜的東東（黑話叫encoding）。圖靈應該看過這篇文章。他很快發現，用樹枝和蛋完全可以模擬出tic-tac-toe。比如說四個蛋表示左上角畫圈。三個蛋一根樹枝, 0001，表示左上角畫X。而且他證明了就算小母雞吃了大力丸能用更復雜的符號在傳送帶上描述tic-tac-toe，也不過比她用樹枝和蛋少花4log(|∑|)倍的時間而已。這里的|∑|代表一共有多少所謂的復雜符號。 於是圖靈寫了帖子，介紹他的雞。後人就把這只雞叫圖靈雞了。 而且人們驚奇地發現，雖然他們做出的機器越來越花哨，下國際象棋能讓大尾巴狼卡斯帕羅夫肝腸寸斷，失意江湖，也不過是一隻擺放樹枝和蛋時快如閃電的圖靈雞而已，和作古的正宗圖靈雞沒有本質區別。我們為了紀念這個現象，就造了一專用名詞，圖靈等價。人們還觀察到有些問題非圖靈雞不可，於是再造一詞：圖靈完備。現在很多老大喜歡把圖靈完備和圖靈等價混用。這好比說命題成立所以逆命題成立，多數時候不靠譜。不過這個話題值得單獨寫一帖子，以後再說吧。
圖靈並不滿足於簡單的2＋3＝5和tic-tac-toe，所以他敏銳地注意到另一個重大挑戰：如果每隻雞都只能做一種計算，他得養多少雞組裝多少傳送帶才能算帳啊？更別說下國際象棋了。人肉計算機圖靈是做化繁為簡的高手。這個高難問題被他舉重若輕地解決了：首先他證明了任何圖靈機都可以用樹枝和蛋表達。然後他養了只更聰明的雞(圖靈搞了N年的數學生理學和形態發生學，大家知道是為什麼了吧？)。這只雞吃腦白金喝農夫山泉，嘛都不幹，不打鳴不下蛋，但會識別理解用樹枝和蛋描述的其它圖靈機，並在傳送帶上模擬它們的操作。用閑人們的黑話總結，就是對任意問題x, 和 , 總存在一隻雞U，使得 。這里的 是用a這串樹枝加蛋的長列表示的圖靈雞。這樣的雞，一隻頂一萬只啊。從此，圖靈不需要再養那麼多雞了，他只需用樹枝和蛋擺出算帳的方法，和提供數據，這只雞就能算出結果。想到這里，圖靈只覺元氣充沛，不禁仰天長嘯：I do chicken right. 這只新品種的雞從此被稱為元圖靈雞(Universal Turing Machine)。Universal者，我雞一出百雞殺之意也。元圖靈雞具有重大意義，代表了兩大計算支柱（還有一個是self-reference）：universality，和ality。Universality我們才說了。而ality是說數據和程序本是如來佛祖座前絞在一塊兒的兩根燈芯。比如用樹枝和蛋表示的圖靈雞，你說它是程序呢，還是數據？理論界的元老Martin Davis在他的書里甚至說儲存程序的計算機這一革命性的概念就是起源於這只元圖靈雞。對了，當年英國有圖靈這樣的先驅，造出世界上第一台通用計算機，為什麼到頭來計算機歷史讓美國人獨大呢？說來也是一段讓人嗟嘆的故事。一言以蔽之，籠中雞不如走地雞，走地雞不如野雞。有興趣的可以讀Andy Kessler的How We Got Here。這本書語言之生動，段子之幽默，故事之曲折，史料之有趣，實在不可多得。而且免費。不能不推薦的說。
當然，一隻雞是遠遠不夠的。圖靈在1952年寫了一坨國際象棋程序，當時居然沒有機器能跑動。很快閑人們一窩蜂撲向計算復雜性這個嶄新的研究領域。4、50年前實在是烽煙四起的戰國時代啊，到處是傳奇英雄的傳奇故事。好像隨便什麼領域都有震撼人心的發現。1964年，Alan Cobham和Jack Edmonds在ACM BBS上發帖，說如果一個問題能被一隻圖靈雞用有限步驟解決，而解決的步數是這個問題長度的多項式，那麼這個問題的復雜度就是P。P是Polynomial的縮寫。可惜有些問題的演算法遠比P復雜，比如找出國際象棋對局的最佳策略。不過很快有人提出，有些問題雖然看似復雜，但驗證這些問題的演算法是否正確需要的復雜度卻是P。比如判斷一堆整數裡面有沒有幾個整數的和剛好為0。驗證某個可能答案太簡單了：對答案里的數求和就行，花的時間最多等於這堆整數的個數。於是有達人就想：這樣好辦啊。如果一個問題的備選答案有N個，那我們就養它N只雞，讓每隻雞驗證一個答案。如果每個答案的驗證復雜度都是P，那最終的復雜度不也是P了么？可惜，得到驗證結果前我們不知道哪個候選答案一定正確，也不能確定哪只雞先得到答案，就好像不知道哪個女工先找到旺卡巧克力工廠的金券。為了和普通的圖靈雞區分，閑人們把這種兵團做戰的雞群叫做non-deterministic圖靈雞 。因為用這種圖靈雞能在多項式時間內找到答案，所以我們把這種復雜度叫NP，也就是Non-deterministic Polynomial的簡寫。還是很直觀的吧？很明顯，P是屬於NP的，因為既然我們能在P內找到答案，自然能在P內驗證答案。那有沒有屬於NP但不屬於P的呢？俺就不知道了。如果我知道的話，我就證明了P=NP或P != NP，拿了Cray研究院的100萬美元花紅，到Bora Bora的海灘悠哉游哉地喝Pina Colada樂。
不能證明P是否等於NP沒有打擊閑人們的積極性。不知道是否等於總比知道不等於好吧？所以牛人們還是前赴後繼地探索。於是NP-Hard就被提出來樂。NP-hard的概念也直觀：我不知道你具體有多復雜，但我知道你至少和NP問題一樣復雜。什麼叫一樣復雜呢？於是有牛人提出，反正多項式加上多項式還是多項式。所以可以判斷，如果我們已知一個問題H的演算法並且每一個屬於NP的問題都可以在多項式時間內通過把玩H得出，那H就是NP-hard。也就是說，如果存在一個函數（或者演算法）f, 使得f(H)＝所有NP問題的集合，且計算f(H)的開銷是P，那H就是NP-hard的。當然，我們還是可以讓一隻圖靈雞來執行這個函數，所以有函數f存在被稱為圖靈多項式可歸約（polynomial time Turing recible）如果H同時也屬於NP，那H就是NP-Complete樂。我們可以相對容易地證明，如果有一個問題，哪怕只有一個問題，既屬於NP也屬於P，那整個P和NP就坍塌了，P＝NP。有興趣的老大可以自己證明一下。到了這里，關於復雜性的研究好像被堵死了。確定一個問題是否為NP-Hard，就得證明它能被多項式歸約到所有NP問題。簡直就是mission impossible嘛。就在這存亡之際，出身水牛城安家多倫多的庫克爺爺小宇宙爆發，於1971年證明了SAT問題（也就是判斷什麼樣的集合能讓一個布爾公式為1）屬於NP-Complete。一時間眾生顛倒。有了SAT墊底，我們就不用去對付所有的NP問題，而只需要對付規約到SAT這一相對簡單得多的問題。到目前為止，屬於NP-Complete的問題沒有1000也有500了吧？人們還相繼發現了其它復雜類。這里羅列了幾乎所有的復雜類，共有462種。

❻ 人工智慧通識-科普-圖靈機之可計算性

所有數學問題都可以用計算機來解決嗎？

如 上一篇繁忙的海狸Busy beaver 中所展示的，海狸是否會陷入無法停機的無限循環？這個看似簡單的數學問題就無法完全用計算機來徹底解決，或者說它是不可計算的。

可計算性是指某個數學問題是否可以用計算機 在有限步驟內徹底解決 。

首先必須是數學問題，而不能是 給我做個漢堡包 這種需要真實的實體變化的問題。

其次必須是有限步驟，如果這個問題的演算法遠遠超過計算機目前可能擁有的計算能力，那麼也應該視為不可計算的。

研究問題的可計算性質可以避免浪費時間在無底的坑裡面做無意掙扎。

可計算性是針對問題而言的，問題又主要是以下兩類：

另外還有 搜索問題Search Problem (在對象Y中是否能夠找到符合要求的結構x)和 最優化問題Optimization Problem (多個解決方案中哪一個更優）。

圖靈機是一種抽象的計算模型，理論上可以實現無限多種演算法，類似的計算模型（功能模型Functional models）還有以下幾個，他們都被認為是 圖靈等價或圖靈完整Turing completeness 的：

如上所示，遞歸理論起源於20世紀30年代，由庫爾特·哥德爾KurtGödel，阿隆佐·邱奇Alonzo Church，羅莎·培特RózsaPéter，阿蘭·圖靈Alan Turing，斯蒂芬·克萊尼Stephen Kleene和埃米爾·珀斯特Emil Post等人提出。

早在1936年就邱奇和圖靈就受到哥德爾的不完備性定理的啟發，演算法程序不可能正確的判斷任意數學問題的真假。後來這個理論就被稱為Church-Turing論文，定義了可計算概念的含義：可由演算法計算的函數都是可計算函數。

可計算性的提出，也意味著科學家們對不可計算問題的認可，證明了數學中確實存在無法有效解決的問題。

此外還有描述可計算程度的相對可計算性Relative computability 和圖靈度Turing degrees。

END

❼ 圖靈機的核心貢獻是什麼

圖靈提出的著名的圖靈機模型為現代計算機的邏輯工作方式奠定了基礎。

圖靈機它相當於通用計算機地解釋程序，這一點直接促進了後來通用計算機的設計和研製工作，在給出通用圖靈機的同時。

圖靈就指出，通用圖靈機在計算時，其「機械性地復雜性」是有臨界限度地，超過這一限度，就要靠增加程序的長度和存貯量來解決.這種思想開啟了後來計算機科學中計算復雜性理論的先河。

圖靈恢復在理論計算機科學方面的研究，並結合戰時的工作，具體研製出新地計算機來。同年，圖靈開始從事「自動計算機」的邏輯設計和具體研製工作，制出了樣機。

(7)圖靈機演算法擴展閱讀

圖靈機的意義：

1、它證明了通用計算理論，肯定了計算機實現的可能性，同時它給出了計算機應有的主要架構。

用類似有限狀態機的原理（注意僅是類似，因為圖靈機的功能遠超過了有限狀態機）定義了「有限次運算」，並用圖靈機運算過程定義了「可行的過程」並將之重新命名為「演算法」（algorithm）。這便是如今計算機體系結構以及程序演算法設計最開始萌芽的地方。

2、圖靈機模型引入了讀寫與演算法與程序語言的概念，極大的突破了過去的計算機器的設計理念。

演算法是一個古老的數學概念，演算法事實上是解題的系統步驟。艾倫・圖靈在1936年提出的「圖靈機」概念,是一般演算法的典型代表。

其目的是為了解決「希爾伯特第十問題」———數學問題的一般演算法步驟問題,也就是在原則上是否存在一般數學問題的解題步驟的判決問題。希爾伯特的規劃是要把數學置於無懈可擊的牢固的基礎上,其中的公理和步驟法則一旦確立就不再改變。他想一勞永逸地解決數學的可靠性問題。

3、圖靈機模型理論是計算學科最核心的理論，因為計算機的極限計算能力就是通用圖靈機的計算能力，很多問題可以轉化到圖靈機這個簡單的模型來考慮。

通用圖靈機等於向我們展示這樣一個過程：程序和其輸入可以先保存到存儲帶上，圖靈機就按程序一步一步運行直到給出結果，結果也保存在存儲帶上。另外，我們也可以看到現代計算機主要構成（馮.諾依曼結構），存儲器，中央處理器，IO系統。

❽ 圖靈在計算機發展史上的主要貢獻有哪些

它的意義有如下幾點:

1、它證明了通用計算理論，肯定了計算機實現的可能性，同時它給出了計算機應有的主要架構；

2、圖靈機模型引入了讀寫與演算法與程序語言的概念，極大的突破了過去的計算機器的設計理念；

3、圖靈機模型理論是計算學科最核心的理論，因為計算機的極限計算能力就是通用圖靈機的計算能力，很多問題可以轉化到圖靈機這個簡單的模型來考慮。

通用圖靈機向人們展示這樣一個過程:程序和其輸入可以先保存到存儲帶上，圖靈機就按程序一步一步運行直到給出結果，結果也保存在存儲帶上。更重要的是，隱約可以看到現代計算機主要構成，尤其是馮・諾依曼理論的主要構成。

圖靈機簡介：

圖靈機是中央處理器（CPU）的一般示例，該處理器控制計算機完成的所有數據操作，而規范機則使用順序存儲器來存儲數據。更具體地說，它是一種能夠枚舉字母表中有效字元串的任意子集的機器（自動機）；這些字元串是遞歸枚舉集的一部分。圖靈機具有無限長的磁帶，可以在其上執行讀取和寫入操作。

假設黑匣子，圖靈機無法知道它最終是否會使用給定程序枚舉子集的任何特定字元串。這是由於無法解決暫停問題，這對計算的理論限制具有重大意義。

Turing機器能夠處理不受限制的語法，這進一步意味著它能夠以無數種方式穩健地評估一階邏輯。通過lambda演算可以證明這一點。

能夠模擬任何其他圖靈機的圖靈機稱為通用圖靈機（UTM，或簡稱為通用機）。用類似的「通用」性質更數學導向的定義是由引進邱奇，上演算，其工作的正式理論與圖靈的交織在一起計算被稱為教會圖靈論題。

❾ 什麼是圖靈機和通用計算機

圖靈機，又稱圖靈計算機，即將人們使用紙筆進行數學運算的過程進行抽象，由一個虛擬的機器替代人類進行數學運算。對於任意一個圖靈機，因為它的描述是有限的，因此總可以用某種方式將其編碼為字元串。，用 <M> 表示圖靈機 M 的編碼。

通用計算機是指各行業、各種工作環境都能使用的計算機。通用計算機適應性很強，應用面很廣，但其運行效率、速度和經濟性依據不同的應用對象會受到不同程度的影響。通用計算機不但能辦公，還能做圖形設計、製作網頁動畫、上網查詢資料等。

(9)圖靈機演算法擴展閱讀：

圖靈提出圖靈機的模型的意義：

1、它證明了通用計算理論，肯定了計算機實現的可能性，同時它給出了計算機應有的主要架構；

2、圖靈機模型引入了讀寫與演算法與程序語言的概念，極大的突破了過去的計算機器的設計理念；

3、圖靈機模型理論是計算學科最核心的理論，因為計算機的極限計算能力就是通用圖靈機的計算能力，很多問題可以轉化到圖靈機這個簡單的模型來考慮。