圖靈機的思想與模型簡介課件

1、圖靈機的思想與模型簡介,圖靈機的思想與模型簡介 -圖靈的貢獻 -圖靈機：計算機的理論模型 -指令、數(shù)據(jù)、程序與程序執(zhí)行,馮.諾依曼計算機：機器級程序及其執(zhí)行 2.2.1 圖靈機的思想與模型簡介,圖靈機的思想與模型簡介,圖靈及其貢獻,圖靈(Alan Turing, 19121954)，出生于英國倫敦，19 歲入劍橋皇家學(xué)院，22 歲當(dāng)選為皇家學(xué)會會員。 1937 年，發(fā)表了論文論可計算數(shù)及其在判定問題中的應(yīng)用，提出了圖靈機模型，后來，馮諾依曼根據(jù)這個模型設(shè)計出歷史上第一臺電子計算機。 1950 年，發(fā)表了劃時代的文章：機器能思考嗎?,成為了人工智能的開山之作。 計算機界于1966年設(shè)立了最高榮譽

2、獎：ACM 圖靈獎,圖靈是誰,你能查閱一下哪些人獲得圖靈獎了嗎？因為什么貢獻而獲獎呢,圖靈機的思想與模型簡介,所謂計算就是計算者(人或機器)對一條兩端可無限延長的紙帶上的一串0或1，執(zhí)行指令一步一步地改變紙帶上的0或1，經(jīng)過有限步驟最后得到一個滿足預(yù)先規(guī)定的符號串的變換過程,計算,10001110110,10001,由“程序”控制，一步步將輸入“轉(zhuǎn)換”為輸出,輸入,輸出,程序,通用機器,圖靈認為什么是計算,圖靈機的思想與模型簡介,圖靈機的思想 是關(guān)于數(shù)據(jù)、指令、程序及程序/指令自動執(zhí)行的基本思想。 輸入被制成一串0和1的紙帶，送入機器中-數(shù)據(jù)。如011 機器可對輸入紙帶執(zhí)行的基本動作包括：“翻

3、轉(zhuǎn)0為1”，或 “翻轉(zhuǎn)1為0”, “前移一位”, “停止”。 對基本動作的控制-指令，機器是按照指令的控制選擇執(zhí)行哪一個動作，指令也可以用0和1來表示：01表示“翻轉(zhuǎn)0為1”(當(dāng)輸入為1時不變)，10表示“翻轉(zhuǎn)1為0”(當(dāng)輸入0時不變), 11表示“前移一位”, 00表示“停止”。 輸入如何變?yōu)檩敵龅目刂瓶梢杂弥噶罹帉懸粋€程序來完成, 如: 011110110111011100 機器能夠讀取程序，按程序中的指令順序讀取指令， 讀一條指令執(zhí)行一條指令。由此實現(xiàn)自動計算,圖靈機的思想與模型簡介,基本的圖靈機模型為一個七元組,如右圖示意 幾點結(jié)論: (1) 圖靈機是一種思想模型，它由一個控制器(有限

4、狀態(tài)轉(zhuǎn)換器)，一條可無限延伸的帶子和一個在帶子上左右移動的讀寫頭構(gòu)成。 (2) 程序是五元組形式的指令集。其定義了機器在一個特定狀態(tài)q下從方格中讀入一個特定字符X時所采取的動作為在該方格中寫入符號Y, 然后向右移一格R (或向左移一格L或不移動N), 同時將機器狀態(tài)設(shè)為p供下一條指令使用,圖靈機是什么,圖靈機模型,圖靈機的思想與模型簡介,圖靈機模型示例。 (注:圓圈內(nèi)的是狀態(tài)，箭線上的是，其含義見前頁,執(zhí)行過程,功能：將一串1的后面再加一位1,控制器,S1,S2,S3,S4,1,1,R,1,1,R,0,1,L,1,1,L,0,0,N,S1：開始狀態(tài) S2：右移狀態(tài) S3：左移狀態(tài) S4：停機狀態(tài),0,0,R,S1,0,0,R,S1,S1,1,1,R,S2,S2,1,1,R,S2,S2,0,1,L,S3,S3,1,1,L,S3,S3,0,0,N,S4,圖靈機的思想與模型簡介,幾點結(jié)論(續(xù)): (3)圖靈機模型被認為是計算機的基本理論模型 -計算機是使用相應(yīng)的程序來完成任何設(shè)定好的任務(wù)。圖靈機是一種離散的、有窮的、構(gòu)造性的問題求解思路，一個問題的求解可以通過構(gòu)造其圖靈機(即程序)來解決。 (4)圖靈認為：凡是能用算法方法