lambda演算 和圖靈機(jī)

1、報(bào)告內(nèi)容 使用演算的計(jì)算和圖靈機(jī)模型完成簡(jiǎn)單的加法運(yùn)算。 說(shuō)明演算的計(jì)算能力與圖靈機(jī)的計(jì)算能力等價(jià)。1.演算 演算（lambda calculus）是一套用于研究函數(shù)定義、函數(shù)應(yīng)用和遞歸的形式系統(tǒng)。它由阿隆佐邱奇和他的學(xué)生斯蒂芬科爾克萊尼在20世紀(jì)30年代發(fā)明的。 演算可以被稱為最小的通用程序設(shè)計(jì)語(yǔ)言。它包括一條變換規(guī)則（變量替換）和一條函數(shù)定義方式。 演算表達(dá)了兩個(gè)計(jì)算機(jī)計(jì)算中最基本的概念“代入”和“置換”。“代入”我們一般理解為函數(shù)調(diào)用，或者是用實(shí)參代替函數(shù)中的形參；“置換”我們一般理解為變量換名規(guī)則?！按搿本褪怯胠ambda演算中的-歸約概念。而“替換”就是lambda演算中的-變換。

2、 表達(dá)式的唯一形式：x，ye，f(a) 例如：f(x,y)=x+y xyx+y 函數(shù)求值： f(2,3)可以表示為： (xyx+y) 2 3 (y2+y)3 2+3 如上已經(jīng)完成了普通加法，這樣就結(jié)束了？ lambda演算系統(tǒng)中合法的字符如下： x1，x2，x3，.xn 變?cè)?歸約 等價(jià) ，（，） 所有能夠在lambda演算系統(tǒng)中出現(xiàn)的合法符號(hào)只有以上四種，其他符號(hào)都是非法的。例如x.x+2，如果沒(méi)有其他對(duì)于符號(hào)的說(shuō)明，那么這就是一個(gè)非法的演算表達(dá)式。 同時(shí)，自然數(shù) 2 也需要定義。 在 lambda 演算中有許多方式都可以定義自然數(shù)，但最常見(jiàn)的還是邱奇數(shù) Church數(shù) 邱奇編碼是把數(shù)據(jù)和運(yùn)

3、算符嵌入到lambda演算內(nèi)的一種方式，它是使用lambda符號(hào)的自然數(shù)的表示法。這種方法得名于阿隆佐邱奇，他首先以這種方法把數(shù)據(jù)編碼到lambda演算中。 Church數(shù)是在Church編碼下的自然數(shù)的表示法。表示自然數(shù)n的高階函數(shù)是把任何其他函數(shù) f 映射到它的n重函數(shù)復(fù)合 的函數(shù)。 lambda演算中的數(shù)字n就是一個(gè)把函數(shù) f 作為參數(shù)并以 f 的n次冪為返回值的函數(shù)。在在演算中，計(jì)算系統(tǒng)演算中，計(jì)算系統(tǒng)用函數(shù)的嵌套次數(shù)來(lái)計(jì)數(shù)。用函數(shù)的嵌套次數(shù)來(lái)計(jì)數(shù)。 PLUS 3 2= m.n.f.x.( (m f)(n f) x) ) 3 2 /將3和2應(yīng)用于m,n這兩個(gè)自由變量=f.x.( (3

4、f) (2 f) x) ) /(2 f) x) = (f.x.(f (f x) f x) = f (f x)=f.x.( (3 f) (f (f x) ) /3=f.x.f (f (f x)=f.x.( (f.x.f (f (f x) f )(f (f x) ) /將f 和 (f (f x) 應(yīng)用于f和x上=f.x.(f (f (f (f (f x) /正好等于5的邱奇數(shù)定義2.圖靈機(jī) 圖靈機(jī)基本模型有一個(gè)有窮控制器，一條輸入帶和一個(gè)帶頭，帶被分成許多單元，帶頭在每個(gè)時(shí)刻掃視帶上的一個(gè)單元。 它工作的時(shí)候是這樣的：從讀寫(xiě)頭在紙帶上讀出一個(gè)方格的信息，并且根據(jù)它當(dāng)前的內(nèi)部狀態(tài)開(kāi)始對(duì)程序進(jìn)行查表，

5、然后得出一個(gè)輸出動(dòng)作，也就是是否往紙帶上寫(xiě)信息，還是移動(dòng)讀寫(xiě)頭到下一個(gè)方格。程序也會(huì)告訴它下一時(shí)刻內(nèi)部狀態(tài)轉(zhuǎn)移到哪一個(gè)。 具體的程序就是一個(gè)列表，也叫做規(guī)則表，是這樣的： 當(dāng)前內(nèi)部狀態(tài)s輸入數(shù)值i 輸出動(dòng)作o下一時(shí)刻的內(nèi)部狀態(tài)sq01前移q1q10往紙帶上寫(xiě)qnq20后移qy 簡(jiǎn)單說(shuō)完成加法的圖靈機(jī)的輸入字符集是0、1和+。帶字符集是0、1、+、=、還有空白符。 圖靈機(jī)程序計(jì)算加法的過(guò)程： 一開(kāi)始帶上內(nèi)容是一個(gè)二進(jìn)制加式，比如2+3，讀寫(xiě)頭在右邊的 1 上。bb10+11=b 首先，圖靈機(jī)將讀寫(xiě)頭運(yùn)動(dòng)到更右一個(gè)位置，寫(xiě)下 =，然后運(yùn)動(dòng)到原始位置。 開(kāi)始向右掃描。讀到 1 或 0，通過(guò)進(jìn)入不同的狀態(tài)記住讀到的是 1 還是 0，把已讀過(guò)的字符記成已讀狀態(tài)。 然后往右找 + ，找到后，再往右找 1 或 0，還是把讀過(guò)的字符標(biāo)記成已讀狀態(tài)。找到后憑借進(jìn)入不同的狀態(tài)記住已讀到的兩個(gè)加數(shù)分別是什么。 然后再往右找 =，找到后在 = 右邊第一個(gè)非 0 或 1 的空位寫(xiě)下記住的兩個(gè)加數(shù)的和。3.演算的計(jì)算