亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

圖靈的基本思想

圖靈的基本思想是用機(jī)器來模擬人們用紙筆進(jìn)行數(shù)算的過程，他把這樣的過程看作下列兩種簡單的動作：

在紙上寫上或擦除某個(gè)符號；

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

而在每個(gè)階段，人要決定下一步的動作，依賴于（a）此人當(dāng)前所關(guān)注的紙上某個(gè)位置的符號和（b）此人當(dāng)前思維的狀態(tài)。

  在某些模型中，紙帶移動，而未用到的紙帶真正是“空白”的。要進(jìn)行的指令（ q4 ）展示在掃描到方格之上（由Kleene（1952）p.375繪制）。

  在某些模型中，讀寫頭沿著固定的紙帶移動。要進(jìn)行的指令（ q1 ）展示在讀寫頭內(nèi)。在這種模型中“空白”的紙帶是全部為0的。有陰影的方格，包括讀寫頭掃描到的空白，標(biāo)記了1,1,B的那些方格，和讀寫頭符號，構(gòu)成了系統(tǒng)狀態(tài)。（由Minsky（1967）p.121繪制）

為了模擬人的這種運(yùn)算過程，圖靈構(gòu)造出一臺假想的機(jī)器，該機(jī)器由以下幾個(gè)部分組成：

一條無限長的紙帶 TAPE 。紙帶被劃分為一個(gè)接一個(gè)的小格子，每個(gè)格子上包含一個(gè)來自有限字母表的符號，字母表中有一個(gè)特殊的符號 ? ? --> {\displaystyle \square } 表示空白。紙帶上的格子從左到右依次被編號為0, 1, 2, ...，紙帶的右端可以無限伸展。

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

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

一個(gè) 狀態(tài)寄存器 。它用來保存圖靈機(jī)當(dāng)前所處的狀態(tài)。圖靈機(jī)的所有可能狀態(tài)的數(shù)目是有限的，并且有一個(gè)特殊的狀態(tài)，稱為 停機(jī)狀態(tài) 。參見停機(jī)問題。

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

圖靈機(jī)的正式定義

一臺 圖靈機(jī) 是一個(gè)七元有序組 ( Q , Σ Σ --> , Γ Γ --> , δ δ --> , q 0 , q a c c e p t , q r e j e c t ) {\displaystyle (Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{accept},q_{reject})} ，其中 Q , Σ Σ --> , Γ Γ --> {\displaystyle Q,\Sigm有限集合Gamma } 都是有限集合，且滿足

Q {\displaystyle Q} 是非空有窮狀態(tài)集合；

Σ Σ --> {\displaystyle \Sigma } 是非空有窮輸入字母表，其中不包含特殊的空白符 ? ? --> {\displaystyle \square } ；

Γ Γ --> {\displaystyle \Gamma } 是非空有窮帶字母表且 Σ Σ --> ? ? --> Γ Γ --> {\displaystyle \Sigma \subset \Gamma } ；

? ? --> ∈ ∈ --> Γ Γ --> ? ? --> Σ Σ --> {\displaystyle \square \in \Gamma -\Sigma } 為 空白符 ，也是唯一允許出現(xiàn)無限次的字符；

δ δ --> : Q × × --> Γ Γ --> → → --> Q × × --> Γ Γ --> × × --> { L , R , ? ? --> } {\displaystyle \delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R,-\}} 是轉(zhuǎn)移函數(shù)，其中 L , R {\displaystyle L,R} 表示讀寫頭是向左移還是向右移, - 表示不移動；

q 0 ∈ ∈ --> Q {\displaystyle q_{0}\in Q} 是起始狀態(tài)；

q a c c e p t ∈ ∈ --> Q {\displaystyle q_{accept}\in Q} 是接受狀態(tài)。 q r e j e c t ∈ ∈ --> Q {\displaystyle q_{reject}\in Q} 是拒絕狀態(tài)，且 q r e j e c t ≠ ≠ --> q a c c e p t {\displaystyle q_{reject}\neq q_{accept}} 。

圖靈機(jī) M = ( Q , Σ Σ --> , Γ Γ --> , δ δ --> , q 0 , q a c c e p t , q r e j e c t ) {\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{accept},q_{reject})} 將以如下方式運(yùn)作：

開始的時(shí)候?qū)⑤斎敕柎?ω ω --> = ω ω --> 0 ω ω --> 1 … … --> ω ω --> n ? ? --> 1 ∈ ∈ --> Σ Σ --> ? ? --> {\displaystyle \omega =\omega _{0}\omega _{1}\ldots \omega _{n-1}\in \Sigma ^{*}} 從左到右依此填在紙帶的第 0 , 1 , … … --> , n ? ? --> 1 {\displaystyle 0,1,\ldots ,n-1} 號格子上，其他格子保持空白（即填以空白符 ? ? --> {\displaystyle \square } )。 M {\displaystyle M} 的讀寫頭指向第0號格子， M {\displaystyle M} 處于狀態(tài) q 0 {\displaystyle q_{0}} 。機(jī)器開始運(yùn)行后，按照轉(zhuǎn)移函數(shù) δ δ --> {\displaystyle \delta } 所描述的規(guī)則進(jìn)行計(jì)算。例如，若當(dāng)前機(jī)器的狀態(tài)為 q {\displaystyle q} ，讀寫頭所指的格子中的符號為 x {\displaystyle x} ，設(shè) δ δ --> ( q , x ) = ( q ′ , x ′ , L ) {\displaystyle \delta (q,x)=(q",x",L)} ，則機(jī)器進(jìn)入新狀態(tài) q ′ {\displaystyle q"} ，將讀寫頭所指的格子中的符號改為 x ′ {\displaystyle x"} ，然后將讀寫頭向左移動一個(gè)格子。若在某一時(shí)刻，讀寫頭所指的是第0號格子，但根據(jù)轉(zhuǎn)移函數(shù)它下一步將繼續(xù)向左移，這時(shí)它停在原地不動。換句話說，讀寫頭始終不移出紙帶的左邊界。若在某個(gè)時(shí)刻 M {\displaystyle M} 根據(jù)轉(zhuǎn)移函數(shù)進(jìn)入了狀態(tài) q a c c e p t {\displaystyle q_{accept}} ，則它立刻停機(jī)并接受輸入的字符串； 若在某個(gè)時(shí)刻 M {\displaystyle M} 根據(jù)轉(zhuǎn)移函數(shù)進(jìn)入了狀態(tài) q r e j e c t {\displaystyle q_{reject}} ，則它立刻停機(jī)并拒絕輸入的字符串。

注意，轉(zhuǎn)移函數(shù) δ δ --> {\displaystyle \delta } 是一個(gè)部分函數(shù)，換句話說對于某些 q {\displaystyle q} , x {\displaystyle x} ， δ δ --> ( q , x ) {\displaystyle \delta (q,x)} 可能沒有定義，如果在運(yùn)行中遇到下一個(gè)操作沒有定義的情況，機(jī)器將立刻停機(jī)。

圖靈機(jī)的基本術(shù)語

設(shè) M = ( Q , Σ Σ --> , Γ Γ --> , δ δ --> , q 0 , q a c c e p t , q r e j e c t ) {\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{accept},q_{reject})} 是一臺圖靈機(jī)，

M {\displaystyle M} 的 帶描述（tape description） 是一個(gè)函數(shù) F : N → → --> Γ Γ --> {\displaystyle F:\mathbb {N} \to \Gamma } ，其中 F ( i ) {\displaystyle F(i)} 表示 M {\displaystyle M} 的帶上第 i {\displaystyle i} 個(gè)格子中的符號；

M {\displaystyle M} 的 格局（configuration） 是一個(gè)三元組 ( F , q , e ) {\displaystyle (F,q,e)} ，其中 F : N → → --> Γ Γ --> {\displaystyle F:\mathbb {N} \to \Gamma } 是當(dāng)前的帶描述， q ∈ ∈ --> Q {\displaystyle q\in Q} 是當(dāng)前的狀態(tài)， e ∈ ∈ --> N {\displaystyle e\in \mathbb {N} } 是當(dāng)前讀寫頭所處的位置；

設(shè) C 1 = ( F 1 , q 1 , e 1 ) {\displaystyle C_{1}=(F_{1},q_{1},e_{1})} , C 2 = ( F 2 , q 2 , e 2 ) {\displaystyle C_{2}=(F_{2},q_{2},e_{2})} 是 M {\displaystyle M} 的格局，設(shè) δ δ --> ( q 1 , F 1 ( e 1 ) ) = ( q , x , d ) {\displaystyle \delta (q_{1},F_{1}(e_{1}))=(q,x,d)} ，若滿足 q 2 = q {\displaystyle q_{2}=q} ， e 2 = { e 1 ? ? --> 1 d = L e 1 + 1 d = R {\displaystyle e_{2}={\begin{cases}e_{1}-1&d=L\\e_{1}+1&d=R\end{cases}}} 以及 F 2 ( i ) = { F 1 ( i ) i ≠ ≠ --> e 1 x i = e 1 {\displaystyle F_{2}(i)={\begin{cases}F_{1}(i)&i\neq e_{1}\\x&i=e_{1}\end{cases}}} 則稱 M {\displaystyle M} 從格局 C 1 {\displaystyle C_{1}} 產(chǎn)生 格局 C 2 {\displaystyle C_{2}} ，記作 C 1 → → --> M C 2 {\displaystyle C_{1}\to _{M}C_{2}} 。

設(shè) C = ( F , q , e ) {\displaystyle C=(F,q,e)} 為 M {\displaystyle M} 的格局，若 q = q a c c e p t {\displaystyle q=q_{accept}} 則稱 C {\displaystyle C} 為 接受格局 ；若 q = q r e j e c t {\displaystyle q=q_{reject}} 則稱 C {\displaystyle C} 為 拒絕格局 ；接受格局和拒絕格局統(tǒng)稱為 停機(jī)格局 。

設(shè) M {\displaystyle M} 是一臺圖靈機(jī)，將字符串 ω ω --> = ω ω --> 0 ω ω --> 1 … … --> ω ω --> n ? ? --> 1 {\displaystyle \omega =\omega _{0}\omega _{1}\ldots \omega _{n-1}} 作為其輸入，若存在格局序列 C 1 , C 2 , … … --> , C k {\displaystyle C_{1},C_{2},\ldots ,C_{k}} ，使得

C 1 {\displaystyle C_{1}} 是 M {\displaystyle M} 在輸入 ω ω --> {\displaystyle \omega } 上的起始格局，即 C 1 = ( F , q 0 , 0 ) {\displaystyle C_{1}=(F,q_{0},0)} ，其中 F 1 ( i ) = { ω ω --> i 0 ≤ ≤ --> i ≤ ≤ --> n ? ? --> 1 ? ? --> otherwise {\displaystyle F_{1}(i)={\begin{cases}\omega _{i}&0\leq i\leq n-1\\\square &{\mbox{otherwise}}\end{cases}}}

C i → → --> M C i + 1 {\displaystyle C_{i}\to _{M}C_{i+1}} ，其中 i = 1 , 2 , … … --> , k ? ? --> 1 {\displaystyle i=1,2,\ldots ,k-1} ；

C k {\displaystyle C_{k}} 是接受格局。

則稱 M {\displaystyle M} 接受 字符串 ω ω --> {\displaystyle \omega } ，且 C 1 , C 2 , … … --> , C k {\displaystyle C_{1},C_{2},\ldots ,C_{k}} 稱為圖靈機(jī) M {\displaystyle M} 在輸入 ω ω --> {\displaystyle \omega } 上的 接受計(jì)算歷史 。同理，若 C k {\displaystyle C_{k}} 是拒絕格局，則稱 M {\displaystyle M} 拒絕 ω ω --> {\displaystyle \omega } ，且 C 1 , C 2 , … … --> , C k {\displaystyle C_{1},C_{2},\ldots ,C_{k}} 稱為圖靈機(jī) M {\displaystyle M} 在輸入 ω ω --> {\displaystyle \omega } 上的 拒絕計(jì)算歷史 。 M {\displaystyle M} 所接受的所有字符串的集合稱為 M {\displaystyle M} 的 語言 ，記作 L ( M ) {\displaystyle L(M)} 。

圖靈機(jī)的例子

設(shè) M = ( { 0 , 1 , 10 , 11 } , { 0 , 1 } , { 0 , 1 , ? ? --> } , δ δ --> , 0 , , ) {\displaystyle M=(\{0,1,10,11\},\{0,1\},\{0,1,\square \},\delta ,0,,)} 和 δ δ --> : { 0 , 1 , 10 , 11 } × × --> { 0 , 1 } → → --> { 0 , 1 , 10 , 11 } × × --> { 0 , 1 } × × --> { R , L , E , S } {\displaystyle \delta :\{0,1,10,11\}\times \{0,1\}\to \{0,1,10,11\}\times \{0,1\}\times \{R,L,E,S\}} . 比如做一個(gè)以1的個(gè)數(shù)表示數(shù)值的加法運(yùn)算，在磁帶上的數(shù)據(jù)是0000001110110000，就是3+2的意思。程序 δ δ --> {\displaystyle \delta } 如下：

第一行程序0,0->0,0R意思就是如果機(jī)器讀到0，就將其變成0，狀態(tài)變?yōu)?，讀寫頭向右移動一格. R就是向右移動一格，L就是向左移一格，E是錯(cuò)誤，S是停機(jī). xx,y -> aa,b中xx是當(dāng)前狀態(tài), y是當(dāng)前格子的值, aa是程序下一步的狀態(tài), b是當(dāng)前格的修改值。

雖然這里給出與上面不同形式的定義，但兩者是等價(jià)的，這里的定義能完成的工作并不比上面的定義多。

通用圖靈機(jī)

對于任意一個(gè)圖靈機(jī)，因?yàn)樗拿枋鍪怯邢薜模虼宋覀兛偪梢杂媚撤N方式將其編碼為字符串。我們用 ? ? --> M ? ? --> {\displaystyle \langle M\rangle } 表示圖靈機(jī) M {\displaystyle M} 的編碼。

我們可以構(gòu)造出一個(gè)特殊的圖靈機(jī)，它接受任意一個(gè)圖靈機(jī) M {\displaystyle M} 的編碼 ? ? --> M ? ? --> {\displaystyle \langle M\rangle } ，然后模擬 M {\displaystyle M} 的運(yùn)作，這樣的圖靈機(jī)稱為 通用圖靈機(jī) （Universal Turing Machine）?，F(xiàn)代電子計(jì)算機(jī)其實(shí)就是這樣一種通用圖靈機(jī)，它能接受一段描述其他圖靈機(jī)的程序，并運(yùn)行程序?qū)崿F(xiàn)該程序所描述的算法。

圖靈機(jī)的變體

圖靈機(jī)有很多變種，但可以證明這些變種的計(jì)算能力都是等價(jià)的，即它們識別同樣的語言類。證明兩個(gè)計(jì)算模型 A {\displaystyle A} 和 B {\displaystyle B} 的計(jì)算能力等價(jià)的基本思想是：用 A {\displaystyle A} 和 B {\displaystyle B} 相互模擬，若 A {\displaystyle A} 可模擬 B {\displaystyle B} 且 B {\displaystyle B} 可模擬 A {\displaystyle A} ，顯然他們的計(jì)算能力等價(jià)。注意這里我們暫時(shí)不考慮計(jì)算的效率，只考慮計(jì)算的理論上“可行性”。

首先我們可以發(fā)現(xiàn)，改變圖靈機(jī)的帶字母表并不會改變其計(jì)算能力。例如我們可以限制圖靈機(jī)的帶字母表為 { 0 , 1 } {\displaystyle \{0,1\}} ，這并不會改變圖靈機(jī)的計(jì)算能力，因?yàn)槲覀冿@然可以用帶字母表為 { 0 , 1 } {\displaystyle \{0,1\}} 的圖靈機(jī)模擬帶字母表為任意有限集合 Γ Γ --> {\displaystyle \Gamma } 的圖靈機(jī)。

另一個(gè)要注意的是，如果我們允許圖靈機(jī)的紙帶兩端都可以無限伸展，這并不能增加圖靈機(jī)的計(jì)算能力，因?yàn)槲覀冿@然可以用只有紙帶一端能無限伸展的圖靈機(jī)來模擬這種紙帶兩端都可以無限伸展的圖靈機(jī)。

如果我們允許圖靈機(jī)的讀寫頭在某一步保持原地不動，那也不會增加其計(jì)算能力，因?yàn)槲覀兛梢杂孟蜃笠苿右淮卧傧蛴乙苿右淮蝸泶嬖谠夭粍印?/span>

其它的常見圖靈機(jī)變種包括：

多帶圖靈機(jī)

非確定型圖靈機(jī)

交替式圖靈機(jī)

枚舉器

圖靈可計(jì)算性

圖靈可識別語言

圖靈可判定語言

遞歸可枚舉語言

可計(jì)算函數(shù)

遞歸函數(shù)

停機(jī)問題

可判定性

不可判定性

不可解度

其它等價(jià)的計(jì)算模型

除了圖靈機(jī)以外，人們還發(fā)明了很多其它的計(jì)算模型。包括：

寄存器機(jī)

遞歸函數(shù)

λ演算

生命游戲

馬爾可夫算法

然而這些模型無一例外地都和圖靈機(jī)的計(jì)算能力等價(jià)，因此邱奇，圖靈和哥德爾提出了著名的邱奇-圖靈論題：一切 直覺上能計(jì)算 的函數(shù)都可用圖靈機(jī)計(jì)算，反之亦然。

參考文獻(xiàn)

Turing, A.,On Computable Numbers, With an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reprinted in M. David（ed.）, The Undecidable, Hewlett, NY: Raven Press, 1965;

Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997. ISBN 0-534-94728-X

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。