lambda演算 和圖靈機

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

2、 表達式的唯一形式：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 變元 歸約 等價 ，（，） 所有能夠在lambda演算系統(tǒng)中出現(xiàn)的合法符號只有以上四種，其他符號都是非法的。例如x.x+2，如果沒有其他對于符號的說明，那么這就是一個非法的演算表達式。 同時，自然數(shù) 2 也需要定義。 在 lambda 演算中有許多方式都可以定義自然數(shù)，但最常見的還是邱奇數(shù) Church數(shù) 邱奇編碼是把數(shù)據(jù)和運

3、算符嵌入到lambda演算內(nèi)的一種方式，它是使用lambda符號的自然數(shù)的表示法。這種方法得名于阿隆佐邱奇，他首先以這種方法把數(shù)據(jù)編碼到lambda演算中。 Church數(shù)是在Church編碼下的自然數(shù)的表示法。表示自然數(shù)n的高階函數(shù)是把任何其他函數(shù) f 映射到它的n重函數(shù)復(fù)合 的函數(shù)。 lambda演算中的數(shù)字n就是一個把函數(shù) f 作為參數(shù)并以 f 的n次冪為返回值的函數(shù)。在在演算中，計算系統(tǒng)演算中，計算系統(tǒng)用函數(shù)的嵌套次數(shù)來計數(shù)。用函數(shù)的嵌套次數(shù)來計數(shù)。 PLUS 3 2= m.n.f.x.( (m f)(n f) x) ) 3 2 /將3和2應(yīng)用于m,n這兩個自由變量=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ù)它當前的內(nèi)部狀態(tài)開始對程序進行查表，

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