計算理論1圖靈機(jī)的變形2從不同的方面對TM

進(jìn)行擴(kuò)充。多帶TM允許TM有多于一條的輸入帶。此時每條帶上將有一個讀頭。不確定的TM

允許TM

在某一狀態(tài)下根據(jù)讀入的符號選擇地進(jìn)行某一個動作：進(jìn)入某個狀態(tài)，在讀頭的當(dāng)前位置印刷某個符號，將讀頭移向某個方向。枚舉器通用圖靈機(jī)它們與基本的TM

等價。通用圖靈機(jī)3通用TM

(universal

Turing

machine)實現(xiàn)對所有TM

的模擬。編碼系統(tǒng)它可以在實現(xiàn)對TM的表示的同時，實現(xiàn)對該TM處理的句子的表示。用0和1對這些除空白符以外的其他的帶符號進(jìn)行編碼。同時也可以用0

和1

對TM

的移動函數(shù)進(jìn)行編碼。通用圖靈機(jī)4設(shè)TM

M2=({q1,q2,q3,q4},{0,1},{0,1,B},

δ,q4,B

,{q3})，其中δ的定義如下:δ(q4,

0)

=

(q4,

0,

R)δ(q4,

1)

=

(q1,

1,

R)δ(q1,

0)

=

(q1,

0,

R)δ(q1,

1)

=

(q2,

1,

R)δ(q2,

0)

=

(q2,

0,

R)δ(q2,

1)

=

(q3,

1,

R)編碼為0

00

0100100010010111通用

TM

檢查

M

是否接受字符串

001101110 0

000100100010010111

001101110主要內(nèi)容5丘奇—圖靈論題圖靈機(jī)的形式化定義圖靈機(jī)的例子圖靈機(jī)的變形多帶圖靈機(jī)非確定型圖靈機(jī)枚舉器與其他模型的等價性算法的定義希爾伯特問題描述圖靈機(jī)的術(shù)語算法的定義6非形式地說，算法是通過有限多次運算就可以決定的過程。算法在數(shù)學(xué)中也起著重要的作用。古代數(shù)學(xué)文獻(xiàn)中包含了各種各樣任務(wù)的算法描述，如尋找素數(shù)和最大公因子。當(dāng)代數(shù)學(xué)中更是充滿了算法。7復(fù)習(xí)：圖靈機(jī)可判定定義

如果一個語言能被某一圖靈機(jī)判定，則稱該語言3.3

是圖靈可判定的(Turning

decidable)。也稱為遞歸語言?？勺R別與可判定？可識別——不接受字符串時，可能出現(xiàn)循環(huán)；可判定——不會出現(xiàn)循環(huán)。定義3.2如果一個語言能被某一圖靈機(jī)識別，則稱該語言是圖靈可識別的(Turning

recognizable)。也稱為遞歸可枚舉語言。希爾伯特問題(1)81900年希爾伯特提出了23個數(shù)學(xué)問題。其中的第10個問題是關(guān)于算法的。通過有限多次運算就可以決定的過程。一個多項式是一些項的和，其中：每個項都是一個常數(shù)和一些變元的積，此常數(shù)叫系數(shù)（coefficient）。例如，6·x·x·x·y·z·z=6x3yz2是一個項，其系數(shù)是6；6x3yz2+3xy2-x3-10

是一個多項式，它有四個項和三個變元x、y、z多項式的根（root）是對它的變元的一個賦值，使此多項式的值為0。上述多項式的一個根是x=5、y=3和z=0，這個根是整數(shù)根（integral

root），因為所有變元都被賦予整數(shù)值。希爾伯特問題(2)9丘奇-圖靈論題（Church-Turing

thesis）希爾伯特第10問題旨在設(shè)計一個算法來檢測一個多項式是否有整數(shù)根?，F(xiàn)在用上述術(shù)語來重新陳述希爾伯特第10問題，設(shè)D={p

|

p

是有整數(shù)根的多項式}本質(zhì)上，希爾伯特第10個問題是問；集合D是不是可判定的?算法的直覺概念

等于

圖靈機(jī)算法10希爾伯特問題(3)考慮只有一個變元的多項式，如4x3-2x2+x-7。設(shè)D1

={p|

p是有整數(shù)根x的多項式}下面是識別D1

的圖靈機(jī)M1：M1

=“輸入是關(guān)于變元x

的一個多項式p當(dāng)x

相繼被設(shè)置為值0,1,-1,2,-2,3,-3,…時，求p

的值，一旦求得0

值，就接受?！比绻鹥有整數(shù)根，M1最終將找到它，從而接受；如果p

沒有整數(shù)根，則M1

將永遠(yuǎn)運行下去。但是其中k

是P的項數(shù)，Cmax

是多項式里的系數(shù)的最大絕對值,C1

是最高次項的系數(shù)。所以單變元的希爾伯特問題可判定。maxmaxC

1

C

1C

C￡

x

￡

k-

k希爾伯特問題(4)11對于多變元的情形，可以設(shè)計一個類似的圖靈機(jī)M

來識別D，只是M

要檢查多個變元所有可能取的整數(shù)值?？勺R別不可判定描述圖靈機(jī)的術(shù)語12描述的詳細(xì)程度有三種： 形式化描述實現(xiàn)描述

高層次描述圖靈機(jī)的格式和記號13圖靈機(jī)的輸入總是一個串。如果想以一個對象而不是字符串的作為輸入，必須先將那個對象字符串化。對象O的編碼成字符串的記號是<O>。如果有多個對象O1,O2,…,Ok，它們的編碼是一個串，記為<O1,O2,…,Ok

>。描述圖靈機(jī)算法的格式是帶引號的文字段，且排成鋸齒形狀。算法的第一行描述機(jī)器的輸入。如果輸入描述僅僅被寫成w，則這個串就被當(dāng)作輸入如果輸入描述是一個對象的編碼<A>，則暗示圖靈機(jī)需要首先檢查此輸入是否確實是所要的對象的編碼，如果不是，則拒絕它。將算法分成幾個步驟，每個步驟可能包括圖靈機(jī)計算的許多步，用更深的縮進(jìn)方式來指示算法的分塊結(jié)構(gòu)。描述圖靈機(jī)的術(shù)語（高層次描述）例3.23

設(shè)

A

是由表示連通無向圖的串構(gòu)成的語言?；貞浺幌?，如果一個圖從任意頂點出發(fā)，都可以沿著邊走到其它

所有頂點，則稱這個圖是連通的。記

A

為A

={<G>|

G

是連通無向圖}下面是判定A

的TM

M

的一個高層次描述：M=“輸入是圖G

的編碼<G>：選擇G

的第一個頂點，并標(biāo)記之。重復(fù)下列步驟，直到?jīng)]有新的頂點可作標(biāo)記。對于G的每一個頂點，如果能通過一條邊將其連到另一個已被標(biāo)記的頂點，則標(biāo)記該頂點。掃描G的所有頂點，確定它們是否都已做了標(biāo)記，如果是，則接受，否則拒絕。14描述圖靈機(jī)的