計(jì)算理論導(dǎo)引w7圖靈機(jī)

計(jì)算理論1引言2什么是計(jì)算？計(jì)算機(jī)的基本能力和局限性是什么？g(n)

=

1若p

的展開式中連續(xù)有n個(gè)50

其它情況3引言Alan

M.

Turing

(1912–1954)In

1936,

Turing

introduced

hisabstract

model

for

computation

inhis

article

“On

Computable

Numbers,

withan

application

to

the

Entscheidungsproblem”.At

the

same

time,

Alonzo

Church

publishedsimilar

ideas

and

results.Turing

model

成為理論計(jì)算科學(xué)的標(biāo)準(zhǔn)模型standard

model引言4圖靈機(jī)（TuringMachine，TM），是計(jì)算機(jī)的一種簡(jiǎn)單的數(shù)學(xué)模型。歷史上，馮?諾曼計(jì)算機(jī)的產(chǎn)生就是由圖靈機(jī)誘發(fā)的。丘奇—圖靈論題：一切合理的計(jì)算模型都等同于圖靈機(jī).主要內(nèi)容5丘奇—圖靈論題圖靈機(jī)的形式化定義圖靈機(jī)的例子圖靈機(jī)的變形多帶圖靈機(jī)非確定型圖靈機(jī)枚舉器與其他模型的等價(jià)性算法的定義希爾伯特問(wèn)題描述圖靈機(jī)的術(shù)語(yǔ)63.1

圖靈機(jī)(Turning

Machine)非形式化描述根據(jù)當(dāng)前狀態(tài)和字符xi

，決定寫移轉(zhuǎn)三動(dòng)作-寫

letter,

有存儲(chǔ)器左或右移動(dòng)轉(zhuǎn)移狀態(tài)

可以作循環(huán)語(yǔ)句磁帶相當(dāng)于數(shù)組，可讀寫。這是增加的重要資源internalstate

set

QRL1

0

1

1

_

0

#

1

_

_

每一步，讀寫頭在單向無(wú)窮帶上左右移動(dòng)并讀寫。圖靈機(jī)state

q0w1

w2

wn

_

_

_

初始,帶子上只有輸入串w?

S*,其它地方是空的。開始狀態(tài)q0。計(jì)算過(guò)程中讀寫頭左右移動(dòng)，機(jī)器內(nèi)部狀態(tài)改變，帶子上內(nèi)容重寫。數(shù)組結(jié)構(gòu)7圖靈機(jī)輸出約定三種輸出：接受、拒絕、循環(huán)state

qacceptv1

v2

vm

_

state

qrejectv1

v2

vm

_

or非常規(guī)意義循環(huán)——不停機(jī)引出可判定性8圖靈機(jī)與有限自動(dòng)機(jī)狀態(tài)控制器aab9相似性：有限狀態(tài)集區(qū)別：(1)圖靈機(jī)在帶子上既能讀也能寫。(2)圖靈機(jī)的讀寫頭既能向左也能向右移動(dòng)。(3)圖靈機(jī)的帶子是無(wú)限長(zhǎng)的。(4)圖靈機(jī)進(jìn)入拒絕和接受狀體將立即停機(jī)。圖靈機(jī)10考慮圖靈機(jī)M1，它檢查語(yǔ)言B

={w#w

|

w∈{0,1}*

}的成員關(guān)系。即設(shè)計(jì)M1，使得如果輸入是B

的成員，它就接受，否則拒絕。(Note:

B是上下文無(wú)關(guān)的嗎？)M1=“對(duì)于輸入字符串w在#兩邊對(duì)應(yīng)的位置上來(lái)回移動(dòng)，檢查這些對(duì)應(yīng)位置是否包含相同的符號(hào)，如不是，或者沒有#，則拒絕，為跟蹤對(duì)應(yīng)的符號(hào)，消去所有檢查過(guò)的符號(hào)。當(dāng)#左邊的所有符號(hào)都被消去時(shí)，檢查#右側(cè)是否還有符號(hào)，如果有則拒絕，否則接受?！盡1

的運(yùn)行示意圖01100#01100X1100#01100X1100#01100X1100#0110011Tape

headmoves

to

rightM1

的運(yùn)行示意圖X1100#01100X1100#01100X1100#X1100X1100#X1100Tape

headmoves

to

left12M1

的運(yùn)行示意圖X1100#X1100X1100#X1100XX100#X1100XX100#X1100Tape

headmoves

to

right13M1

的運(yùn)行示意圖XX100#X1100XX100#X1100XX100#XX100XX100#XX10014Tape

headmoves

to

leftM1

的運(yùn)行示意圖XX100#XX100XX100#XX100XXX00#XX100XXX00#XX10015Tape

headmoves

to

rightM1

的運(yùn)行示意圖XXXXX#XXXX0XXXXX#XXXXXXXXXX#XXXXXXXXXX#XXXXXTape

headmoves

to

left1617M1

的運(yùn)行示意圖XXXXX#XXXXXXXXXX#XXXXXXXXXX#XXXXXXXXXX#XXXXXacceptTape

headmoves

to

right18圖靈機(jī)的形式化定義定義

圖靈機(jī)是一個(gè)

7

元組

(Q,

S,

G,

d,

q0,

qaccept,

qreject)3.1

(1)

Q

是狀態(tài)集。S

是輸入字母表，不包括特殊空白符號(hào)。G

是帶字母表，其中

?

G并且

S

G

。d

:Q×Gfi

Q

×G

×{L,R}是轉(zhuǎn)移函數(shù)。q0

是起始狀態(tài)。qaccept

是接受狀態(tài)。qreject

是拒絕狀態(tài)，qaccept≠qreject。例如d:

(q,

a)

=

(r,

b,

L)19圖靈機(jī)的計(jì)算方式開始時(shí)，M

以最左邊的n

個(gè)帶方格接收輸入w=w1w2…wn?

S*，帶的其余部分保持空白(即填以空白符)，讀寫頭從最左邊的帶方格開始運(yùn)行，注意S

不含空字符，故出現(xiàn)在帶上的第一個(gè)空字符表示輸入的結(jié)束。M開始運(yùn)行后，計(jì)算根據(jù)轉(zhuǎn)移函數(shù)所描述的規(guī)則進(jìn)行，如果M試圖將讀寫頭從帶的最左端再向左移出，即使轉(zhuǎn)移函數(shù)指示的是L，讀寫頭也停在原地不動(dòng)。計(jì)算一直持續(xù)到它進(jìn)入接受狀態(tài)或拒絕狀態(tài)，此時(shí)停機(jī)，如果二者都不發(fā)生，則M

將永遠(yuǎn)運(yùn)行下去。Note：

A

TM

may

never

halt

on

an

specified

input!How

about

DFA,

NFA,

PDA?w1w2……wn圖靈機(jī)的格局圖靈機(jī)計(jì)算過(guò)程中，當(dāng)前狀態(tài)、當(dāng)前帶內(nèi)容和讀寫頭當(dāng)前位置組合在一起，稱為圖靈機(jī)的格局(Configurations)。對(duì)于狀態(tài)q

和帶字母表G

的兩個(gè)字符串u

和v，以u(píng)qv

表示如下格局：當(dāng)前狀態(tài)是q，當(dāng)前帶上的內(nèi)容是uv，讀寫頭的當(dāng)前位置是v

的第一個(gè)符號(hào)，帶上v

的字符最后字符以后的符號(hào)都是空白符。例如，1011q701111101101111q720圖靈機(jī)計(jì)算方式的形式化21如果圖靈機(jī)能合法地從格局C1

一步進(jìn)入C2，則稱格局C1產(chǎn)生格局C2。設(shè)a,b

和c

是G

中的符號(hào)，u和v

是G*

中字符串，qi和qj是狀態(tài)，則uaqibv

和uqjacv

是兩個(gè)格局。如果轉(zhuǎn)移函數(shù)滿足d

(qi

,b)=(qj

,c,L)，則說(shuō)uaqibv

產(chǎn)生和uqjacv

。M

在輸入w

上的起始格局是格局q0w，表示機(jī)器處于起始狀態(tài)q0，并且讀寫頭處于帶子的最左端位置，在接受格局里，狀態(tài)是qaccept

，在拒絕格局里，狀態(tài)是qreject。接受和拒絕狀態(tài)都是停機(jī)狀態(tài)，它們都不再產(chǎn)生新的格局。由于圖靈機(jī)只在接受或拒絕狀態(tài)下才停機(jī)，可以等價(jià)地將狀態(tài)轉(zhuǎn)移函數(shù)簡(jiǎn)化d

:

Q'

×Gfi

Q

×

G

×{

L,

R

}其中Q'是取消qaccept

和qreject

的Q。圖靈機(jī)計(jì)算方式的形式化22圖靈機(jī)M接受輸入w

，如果存在格局的序列Cl,C2,…,Ck使得：Cl

是M

在輸入w上的起始格局；每一個(gè)Ci

產(chǎn)生Ci+1；Ck

是接受格局。M接受的字符串的集合稱為M的語(yǔ)言，或被M識(shí)別的語(yǔ)言，記為L(zhǎng)(M)。23圖靈機(jī)的形式化定義定義3.2如果一個(gè)語(yǔ)言能被某一圖靈機(jī)識(shí)別，則稱該語(yǔ)言是圖靈可識(shí)別的(Turning

recognizable)。也稱為遞歸可枚舉語(yǔ)言。輸入上運(yùn)行一個(gè)TM時(shí)，可能出現(xiàn)三種結(jié)果：接受、拒絕、循環(huán)（僅僅指機(jī)器不停機(jī)）對(duì)于一個(gè)輸入，TM有兩種方式不接受它：一種拒絕狀態(tài)一種進(jìn)入循環(huán)問(wèn)題：如何區(qū)別長(zhǎng)計(jì)算與死循環(huán)？因此，我們喜歡對(duì)所有輸入都停機(jī)的圖靈機(jī)，永不循環(huán)，這種機(jī)器為判定器。因?yàn)樗鼈兛偰軟Q定是接受還是拒絕。24圖靈機(jī)的形式化定義定義3.3如果一個(gè)語(yǔ)言能被某一圖靈機(jī)判定，則稱該語(yǔ)言是圖靈可判定的(Turning

decidable)。也稱為遞歸語(yǔ)言。可識(shí)別與可判定？可識(shí)別——語(yǔ)言內(nèi)的字符串,接受；語(yǔ)言外的字符串可能拒絕，也可能引起圖靈機(jī)循環(huán);可判定——語(yǔ)言外的字符串不會(huì)引起圖靈機(jī)循環(huán)圖靈機(jī)舉例例3.4

描述

TM

M2，它識(shí)別的語(yǔ)言是所有由

0

組成、長(zhǎng)度為

2的方冪的字符串，即

A={

02

|

n

≥0}nM2

=“對(duì)于輸入字符串w：從左往右掃描整個(gè)帶子，隔一個(gè)字符消去一個(gè)0。如果在第1步之后，帶子上只剩下唯一的一個(gè)0，則接受。如果在第1步之后，帶子上包含不止一個(gè)0，并且0的個(gè)數(shù)是奇數(shù)，則拒絕。讀寫頭返回至帶子的最左端。轉(zhuǎn)到第1步?！?5圖靈機(jī)的例子26每重復(fù)一次第1步，消去了一半個(gè)數(shù)的0。由于在第1步中，機(jī)器掃描了整個(gè)帶子，故它能夠知道它看到的0

的個(gè)數(shù)是奇數(shù)還是偶數(shù)，如果是大于1

的奇數(shù)，則輸入中所含的0

的個(gè)數(shù)不可能是2

的方冪，此時(shí)機(jī)器就拒絕。但是，如果看到的0

的個(gè)數(shù)是1，則輸入中所含的0

的個(gè)數(shù)肯定是2

的方冪，此時(shí)機(jī)器就接受。M2=(Q,S,G,d,q1,qaccept,qreject)的形式化描述：Q={q1

,

q2

,

q3

,

q4

,

q5

,

qaccept,

qreject}，S={0}，G={0,x,□}，將d描述成狀態(tài)圖開始、接受和拒絕狀態(tài)分別是q1,qaccept,qreject27圖靈機(jī)舉例q1q3q4qrejectq2qaccept0fi

,

Rfi

Rxfi

Rfi

R0fi

x,

Rxfi

Rxfi

Rfi

L0fi

Rxfi

Rfi

R0fi

x,

Rxfi

L0fi

Lq5fi

R圖靈機(jī)舉例28例3.5

下面給出圖靈機(jī)

M1

形式化描述M1=(Q,

S,G,d,q1,qaccept,qreject)，它的判定語(yǔ)言是B

={w#w

|

w?

{0,

1}*}。Q

=

{

q1,

q2,

…,

q8

,

qaccept,

qreject}，S

=

{

0,

1,

#

}

且

G

=

{

0,

1,

#,

x,

}。用狀態(tài)圖描述d。開始、接受和拒絕狀態(tài)分別是q1,qaccept,qreject。圖靈機(jī)M1的狀態(tài)圖q129q8q3q5q4q7qacceptq2#fiRxfiR□fi

R0,1fi

R#fiRxfiR0,1,xfi

L0,1fi

Lq6#fiLxfiR#fiR0,1fi

RxfiR第一步由q1到q7實(shí)現(xiàn)，第二步由其余狀態(tài)實(shí)現(xiàn)30圖靈機(jī)舉例例3.6

圖靈機(jī)

M3

做一些初等算術(shù)，它判定的語(yǔ)言C

={aibjck

|

i

×j

=k，且i,j,k

≥1}M3=“對(duì)于輸入字符串w：從左往右掃描輸入，確認(rèn)輸入具有形式a*b*c*，否則拒絕。讀寫頭回到帶子的左端點(diǎn)。消去一個(gè)a，并向右掃描直到b出現(xiàn)。在b與c之間來(lái)回 移動(dòng)，成對(duì)地消去b和c，直到把所有的b都消去。如果 c

全消除后還有b，則拒絕。如果還有a

未消去，則恢復(fù)所有已消去的b，再重復(fù)第3步。如果所有的a

都已被消去，則檢查所有的c

是