圖靈機與可計算性

圖靈（1912~1954）出生于英國倫敦，19歲進入劍橋皇家學院研究量子力學和數理邏輯。1935年，圖靈寫出了“論高斯誤差函數”的論文，因此他從一名學生直接成為學院的研究員，并開始了“可計算性”研究。1936年4月，圖靈發(fā)表了“可計算數及其在判定問題上的一個應用”的論文，形成了“圖靈機”的重要思想。用反證法證明，任何可計算其值的函數都存在相應的圖靈機；反之，不存在相應圖靈機的函數就是不具有可計算其函數值算法的函數。同年，圖靈到美國普林斯頓大學學習，并于1938年獲該校博士學位。1939年秋，圖靈應召到英國外交部通信處從事密碼破譯工作，開始了最早的計算機的研究工作。戰(zhàn)后圖靈一直從事計算機的理論研究和實踐開發(fā)研究，制作出最早的電子計算機。他于1950年發(fā)表了“計算機和潛力”的論文，引發(fā)了“機器是否會思考”的學術討論，并成為影響至今的經典論著。圖靈思想活躍，但性格內向，一直沒有結婚。1954年6月，圖靈在家中因氰化鉀中毒去世，原因則眾說紛紜，至今仍為一個謎。

“算法”（Algorithm）這個名稱最早源于9世紀阿拉伯數學家花拉子米的一本著作，在這本著作中花拉子米用算法來概括算術四則運算的法則。20世紀初，希爾伯特提出了著名的23個數學問題，其中很多都涉及到問題解決的判定問題。1935年，正在劍橋皇家學院讀書的圖靈，在聽了數理邏輯學家紐曼的課程后，開始注意希爾伯特的判定問題，并進行了潛心的研究。該問題要求判定是否存在一種有效的算法（或今天在計算機科學中稱為“程序”的東西），把某個結論從一組給定的假設中用邏輯方法推演出來。圖靈將算法看做一個機械的過程，或者是一組規(guī)則，它規(guī)定了人們在任何情況下必須執(zhí)行的某類操作的指令。

今天的計算機技術，人們將“算法”定義為用特定的計算機語言編寫的計算機程序。然而，圖靈的早期研究則是為了從理論上解決可判定性來定義“算法”，并提出與之相應的圖靈機（理論）。

圖靈機是假設的抽象“計算機”，如圖9.6所示。圖靈機由三個部分組成：一條帶子，一個讀寫頭和一個控制裝置。帶子分成許多小格，每小格可存一位數（0或1），也可以是空白的。機器的運作是按逐步進行的方式，每一步由三個不同的動作組成：在任一確定時刻，讀寫頭對準帶子上的一個方格，根據該格上的內容和機器的狀態(tài)決定自己的動作；機器可以抹去帶上的原有符號，使方格保持空白或者寫上另外的（也可以與原來相同的）符號；然后讓帶子通過讀寫頭，朝兩個方向之一移動一個方格。機器的行為自始至終是由一個指令集所決定，它明確地指示機器每一步應該執(zhí)行哪三個動作。整個運作從讀寫頭視讀第一個方格數據開始，一旦計算結束，機器就進入一個特別的停止狀態(tài)。運算過程的任何結果都被紀錄在帶子上。

圖9.6圖靈機的圖示

圖靈機的行為由算法控制，算法的程序由有限條指令組成，每一條取自下列一組可能的選擇：

PRINT0 ONTHECURRENTSQUARE在當前方格中寫0

PRINT1 ONTHECURRENTSQUARE在當前方格中寫1

GOLEFTONESQUARE左移一格

GORIGHTONESQUARE右移一格

GO TO STEPiIF THECURRENT SQUARECONTAINS0若當前方格內容為0，轉向步i

GO TO STEPjIF THECURRENT SQUARECONTAINS1若當前方格內容為1，轉向步j

STOP停止

由這七種簡單的指令出發(fā)，可以組成所謂的“圖靈一波斯特程序”，通過這些程序控制機器完成各種計算。圖靈機是一個假想的計算模型，并不是一臺實際的機器。從以上介紹可見，它的結構與動作極為簡單，但是，正是這樣簡單的結構包含了現代電子計算機最基本的工作原理：按串行運算、線性儲存方式進行符號處理。

利用可計算性，數學家解決了眾多的判定性問題，存在（或不存在）某種求解的算法，是確定這些判定性問題的標準。顯然算法的存在性判定可以滿足純數學研究的需要。但另一方面，在解決現實問題中，單純的算法存在性的判定是遠遠不夠的。如果一個算法讓高速計算機算上幾千年，那么它就毫無實用的價值。我們必須研究有效算法的存在性，制定算法有效性的評估標準。

20世紀60年代，柯勃漢與愛德華茲創(chuàng)立了算法有效性的一種判定法則：區(qū)分算法是否有效，要以圖靈機為基本的計算工具，用圖靈機上完成計算的步數（即圖靈程序）來評估一個算法是否有效。一般地，人們習慣于依據“計算時間”的長短來判定算法的有效性，使用這種度量標準，需要使用以下的相關定義：

如果存在確定的整數A和k，對于長度為n的輸入數據，計算可以在至多An^k步內完成（對任意的n值）。那么，這個算法被稱為“多項式時間算法?！崩?，將兩個整數相加的標準算法是多項式時間算法。不是多項式時間算法的算法被稱之為“指數時間算法”。當一個算法處理長度為n的輸入數據時，若需要2ⁿ（或3ⁿ，nⁿ，n!）步，它就是一個指數時間算法。

柯勃漢和愛德華茲將“有效”算法規(guī)定為需要多項式時間的算法。而將需要指數時間的算法規(guī)定為“非有效”算法。這種劃分方法只是“理論”的劃分方法，它與實際應用還有一定的區(qū)別。譬如，A=10⁵⁰和k=500的多項式時間算法在實際意義上一般不會“有效”。所幸的是，在現實問題中，一般都取10n³（即A=10，k=3）或更少步數的多項式時間算法或指數時間算法。盡管2ⁿ步算法在“理論上無效”但對適度小的n，2ⁿ的步數完全可以比多項式時間更少。雖然對于不太大的n，多項式函數值可以超過指數函數值，但對于相對大的n，后者總是大于前者。假定一臺計算機每10^-6秒執(zhí)行一次基本運算，對于已知的數據長度n，多項式時間與指數時間算法在計算機上的運行時間如下表：

時間－數據長度：n

復雜性函數102030405060

n0.00001s0.00002s0.00003s0.00004s0.00005s0.00006s

n²0.0001s0.0004s0.0009s0.0016s0.0025s0.0036s

n³0.001s0.008s0.027s0.064s0.125s0.216s

2n0.001s1.0s17.9分12.7天35.7年366世紀

3n0.059s58分6.5年3855世紀2×10⁸世紀1.3×10¹³世紀

目前，人們將多項式時間算法問題稱為P型問題，它是可解的。但是諸如旅行推銷員這類問題還不能說是無解的，而是歸入了稱之為NP型問題，NP意思是“非確定型多項式時間”，這樣P型問題就是NP型問題的子集。為了理解NP這個概念，可以設想有一臺圖靈機或者其他任何一種計算機，它能在運算的各個步驟進行隨機猜想。利用這樣的假想計算機（稱做非確定型圖靈機），推銷員問題就能用多項式時間求解：首先猜測第一個要訪問的城市，然后猜第二個，第三個，如此等等，直到猜完整個旅行路線，然后計算總的路程并與已知旅差費假定值比較。只要機器每一步都“猜測正確”，最后所得的結果也就正確。這就是所謂NP型問題的涵義：通過一次或多次“正確的”（或“最優(yōu)的”）猜想，問題可能在非確定型圖靈機上用多項式時間求解。

由于數學內部與現實中存在著大量的既沒有找到有效算法但又屬于NP型的問題。人們希望解決這些問題的企圖，轉化為P是否能等于NP的理論討論。1971年，庫克借助圖靈和他人的工作，運用抽象的方法證明了“NP型問題極不可能用多項式時間算法求解”。他的解釋是：如果一類特殊的NP型問題（如旅行推銷員問題）可以用多項式算法求解，那么所有NP型問題都可以用多項式時間求解。即庫克認為“P不等于NP”。然而，要獲得問題的最終解決，還需要一個反例，即找出一個屬于NP型問題，又能證明它不是P型的問題，盡管P和NP這兩個概念直覺有別，P不等于NP這個問題，但問題卻還遠沒有得到解決，并且各方面的跡象都表明這是一個極其難以解決的問題。這個以“P=NP”著稱的問題，已經成為當今計算機數學中最重要的未解決問題之一。

圖靈機理論還成為人工智能的研究基礎。根據符號轉換的定義，人腦或計算機進行的定理證明、文字處理和一切可歸結為符號處理的操作，都屬于計算的過程。1947年，圖靈在一次計算機會議上提出有關智能機器的報告，論證了智能機器的可能性。他的這篇報告被編入《機器智能》（1969年）后，人們才認識到它的深刻意義。1950年圖靈又根據計算機能進行符號計算的事實，發(fā)表了《計算機與智力》的重要論文，提出計算機能像人類的思維方式進行思維的觀點，并給出了檢驗計算機是否具有思維的能力的一個實驗，這就是很著名的“圖靈檢驗”。1956年夏，美國的一批年輕的科學家討論了用機器模擬人類智能的問題，提出人工智能的概念。1976年西蒙等人提出了物理符號假設：任何一個系統(tǒng)，如果它能表現出智能，則它必須具備執(zhí)行輸入符號、輸出符號、存儲符號、復制符號、建立符號結構和條件性遷移操作這六種功能。反之，任何能執(zhí)行這六種操作的系統(tǒng)，必然表現出智能，這一假設有三個推論：第一，因為人有智能，所以人是一個符號系統(tǒng)；第二，因為計算機是一個符號系統(tǒng)，所以計算機可以表現出智能；第三，計算機能模擬人的職能。該假設為人工智能提供了一個理論基礎，其核心思想是，智能可以歸結為六種操作符號或計算。

1991年11月8日，波士頓計算機博物館舉行了世界第一次的圖靈試驗，讓人與8種程序計算機交談，話題包括女人的衣著，親屬關系，以及白蘭地酒等。這次實驗將計算機與人的對話變成了現實。

形式化定義

　　一臺圖靈機是一個七元組 (Q,Σ,Γ,δ,q0,qaccept,qreject)，其中 Q,Σ,Γ都是有限集合，且滿足
　　1.Q 是狀態(tài)集合；
　　2.Σ 是輸入字母表，其中不包含特殊的空白符 □；
　　3.Γ 是帶字母表，其中 □∈Γ且Σ∈Γ ；
　　4. δ:Q×「→Q×?！羬L,R}是轉移函數，其中L,R 表示讀寫頭是向左移還是向右移；
　　5.q0∈Q是起始狀態(tài)；
　　6. qaccept是接受狀態(tài)。
　　7.qreject是拒絕狀態(tài)，且 。 qreject≠qaccept
　　圖靈機 M = (Q,Σ,Γ,δ,q0,qaccept,qreject) 將以如下方式運作：
　　開始的時候將輸入符號串 從左到右依此填在紙帶的第 號格子上， 其他格子保持空白(即填以空白符)。 M 的讀寫頭指向第 0 號格子，M 處于狀態(tài) q0。 機器開始運行后，按照轉移函數 δ 所描述的規(guī)則進行計算。 例如，若當前機器的狀態(tài)為q，讀寫頭所指的格子中的符號為 x， 設 δ(q,x) = (q',x',L)， 則機器進入新狀態(tài) q'，將讀寫頭所指的格子中的符號改為 x'， 然后將讀寫頭向左移動一個格子。 若在某一時刻，讀寫頭所指的是第 0 號格子，但根據轉移函數它下一步將繼續(xù)向左移，這時它停在原地不動。 換句話說，讀寫頭始終不移出紙帶的左邊界。 若在某個時刻 M根據轉移函數進入了狀態(tài) qaccept， 則它立刻停機并接受輸入的字符串； 若在某個時刻 M 根據轉移函數進入了狀態(tài) qreject，則它立刻停機并拒絕輸入的字符串。
　　注意，轉移函數 δ 是一個部分函數， 換句話說對于某些 q,x， δ(q,x) 可能沒有定義，如果在運行中遇到下一個操作沒有定義的情況， 機器將立刻停機。

停機問題

　　停機問題（halting problem）是目前邏輯數學的焦點，和第三次數學危機的解決方案。其本質問題是:給定一個圖靈機 T，和一個任意語言集合 S, 是否 T 會最終停機于每一個。其意義相同于可確定語言。顯然任意有限 S是可判定性的，可數的(countable) S 也是可停機的，在使用 oracle 輸入的幫助下。
　　通俗的說，停機問題就是判斷任意一個程序是否會在有限的時間之內結束運行的問題。如果這個問題可以在有限的時間之內解決，可以有一個程序判斷其本身是否會停機并做出相反的行為。這時候顯然不管停機問題的結果是什么都不會符合要求。所以這是一個不可解的問題。
　　停機問題本質是一階邏輯的不自恰性和不完備性。類似的命題有理發(fā)師悖論、全能悖論等。！
　　證明:
　　設停機問題有解，即：存在過程H(P,I)可以給出程序P在輸入I的情況下是否可停機。假設若P在輸入I時可停機，H輸出“停機”，反之輸出“死循環(huán)”，即可導出矛盾：
　　顯然，程序本身可以被視作數據，因此它可以被作為輸入，故H應該可以判定當將P作為P的輸入時，P是否會停機。所以我們設過程K(P)的流程如下：首先，它調用H(P,P)，如果H(P, P)輸出“死循環(huán)”，則K(P)停機，反之K(P)死循環(huán)。即K(P)做與H(P,P)的輸出相反的動作。
　　現在假設求K(K)，則若H(K, K)輸出停機，K(K)死循環(huán)，但由定義知二者矛盾。反之，H(K,K)輸出死循環(huán)，則K(K)停機，兩者一樣矛盾。
　　因此，H不是總能給出正確答案，故而不存在解決停機問題的方法。

通用圖靈機

　　對于任意一個圖靈機，因為它的描述是有限的，因此我們總可以用某種方式將其編碼為字符串。 我們用<M> 表示圖靈機 M 的編碼。
　　我們可以構造出一個特殊的圖靈機，它接受任意一個圖靈機 M 的編碼<M>，然后模擬 M 的運作，這樣的圖靈機稱為通用圖靈機(Universal TuringMachine)。現代電子計算機其實就是這樣一種通用圖靈機的模擬，它能接受一段描述其他圖靈機的程序，并運行程序實現該程序所描述的算法。但要注意,它只是模擬,因為現實中的計算機的存儲都是有限的，所以無法跨越有限狀態(tài)機的界限。

變體

　　圖靈機有很多變種，但可以證明這些變種的計算能力都是等價的，即它們識別同樣的語言類。證明兩個計算模型 A 和 B 的計算能力等價的基本思想是： 用 A 和 B 相互模擬， 若 A 可模擬 B 且 B 可模擬 A，顯然他們的計算能力等價。注意這里我們暫時不考慮計算的效率，只考慮計算的理論上“可行性”。
　　首先我們可以發(fā)現，改變圖靈機的帶字母表并不會改變其計算能力。例如我們可以限制圖靈機 的帶字母表為{0,1}，這并不會改變圖靈機的計算能力，因為我們顯然可以用帶字母表為 {0,1} 的圖靈機模擬帶字母表為任意有限集合 Γ的圖靈機。
　　另一個要注意的是，如果我們允許圖靈機的紙帶兩端都可以無限伸展，這并不能增加圖靈機的計算能力，因為我們顯然可以用只有紙帶一端能無限伸展的圖靈機來模擬這種紙帶兩端都可以無限 伸展的圖靈機。
　　如果我們允許圖靈機的讀寫頭在某一步保持原地不動，那也不會增加其計算能力，因為我們可以用向左移動一次再向右移動一次來代替在原地不動。
　　其它的常見圖靈機變種包括：
　　多帶圖靈機
　　非確定型圖靈機
　　枚舉器

圖靈可計算性

　　圖靈可識別語言
　　圖靈可判定語言
　　遞歸可枚舉語言
　　可計算函數
　　遞歸函數
　　停機問題
　　可判定性
　　不可判定性

其它等價的計算模型

　　除了圖靈機以外，人們還發(fā)明了很多其它的計算模型。包括：
　　寄存器機
　　遞歸函數
　　λ演算
　　生命游戲
　　馬爾可夫算法
　　然而這些模型無一例外地都和圖靈機的計算能力等價，因此邱奇，圖靈和哥德爾提出了著名的邱奇-圖靈論題：一切直覺上能行可計算的函數都可用圖靈機計算，反之亦然。

NP："非確定性圖靈機下"的多項式算法

舉個例子.

1. 沒有.繼續(xù)猜測“可能在你爸的抽屜里”,...,尋找...
2. 有.

關于P，NP，NPC和NP-hard的通俗解釋

圖靈機

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

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

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

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

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

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

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

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

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

自動機
automata

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

圖靈機（英語：Turing Machine，又稱確定型圖靈機）是英國數學家阿蘭·圖靈于1936年提出的一種抽象計算模型，其更抽象的意義為一種數學邏輯機，可以看作等價于任何有限邏輯數學過程的終極強大邏輯機器。

一臺圖靈機是一個七元組 (Q,Σ,Γ,δ,q0,qaccept,qreject)，其中 Q,Σ,Γ 都是有限集合，且滿足
Q 是狀態(tài)集合；
Σ 是輸入字母表，其中不包含特殊的空白符 ；
Γ 是帶字母表，其中 且 ；
是轉移函數，其中L,R 表示讀寫頭是向左移還是向右移；
是起始狀態(tài)；
是接受狀態(tài)。
是拒絕狀態(tài)，且 。
圖靈機 M = (Q,Σ,Γ,δ,q0,qaccept,qreject) 將以如下方式運作：
開始的時候將輸入符號串 從左到右依此填在紙帶的第 號格子上， 其他格子保持空白(即填以空白符)。 M 的讀寫頭指向第 0 號格子， M 處于狀態(tài) q0。 機器開始運行后，按照轉移函數 δ 所描述的規(guī)則進行計算。 例如，若當前機器的狀態(tài)為 q，讀寫頭所指的格子中的符號為 x， 設 δ(q,x) = (q',x',L)， 則機器進入新狀態(tài) q'， 將讀寫頭所指的格子中的符號改為 x'， 然后將讀寫頭向左移動一個格子。 若在某一時刻，讀寫頭所指的是第 0 號格子， 但根據轉移函數它下一步將繼續(xù)向左移，這時它停在原地不動。 換句話說，讀寫頭始終不移出紙帶的左邊界。 若在某個時刻 M 根據轉移函數進入了狀態(tài) qaccept， 則它立刻停機并接受輸入的字符串； 若在某個時刻 M 根據轉移函數進入了狀態(tài) qreject， 則它立刻停機并拒絕輸入的字符串。
注意，轉移函數 δ 是一個部分函數， 換句話說對于某些 q,x， δ(q,x) 可能沒有定義， 如果在運行中遇到下一個操作沒有定義的情況， 機器將立刻停機。



參考:http://zh.wikipedia.org/w/index.php?title=圖靈機&variant=zh-cn

?。。》谴_定型圖靈機

http://zh.wikipedia.org/wiki/非確定圖靈機

?。。⌒问秸Z言與自動機第一講

http://wenku.baidu.com/view/c4e551c55fbfc77da269b10b.html

愛華網本文地址 » http://www.klfzs.com/a/25101015/282641.html