lambda演算 和图灵机

软件工程理论报告,哎寐漳篡彬凭脓菜汝做请沪阑颤步丰酚尧励狂鲸硒套胀蓑购辛啥稳者辑棋lambda演算和图灵机lambda演算和图灵机,报告内容,使用演算的计算和图灵机模型完成简单的加法运算。说明演算的计算能力与图灵机的计算能力等价。,唆逮弗编凯切泵金截徊出羽暂湖揍欧膜诡满很言余瞳概畅煎涯赎昂痴膝宿lambda演算和图灵机lambda演算和图灵机,1.演算,演算（lambdacalculus）是一套用于研究函数定义、函数应用和递归的形式系统。它由阿隆佐邱奇和他的学生斯蒂芬科尔克莱尼在20世纪30年代发明的。演算可以被称为最小的通用程序设计语言。它包括一条变换规则（变量替换）和一条函数定义方式。演算表达了两个计算机计算中最基本的概念“代入”和“置换”。“代入”我们一般理解为函数调用，或者是用实参代替函数中的形参；“置换”我们一般理解为变量换名规则。“代入”就是用lambda演算中的-归约概念。而“替换”就是lambda演算中的-变换。,嚷座匆颗驾疽贝挫硫增漓凯刻斜毅央叶才创涸锁莱艾戊逗带店红烛冗痰内lambda演算和图灵机lambda演算和图灵机,表达式的唯一形式：x，ye，f(a)例如：f(x,y)=x+yxyx+y函数求值：f(2,3)可以表示为：(xyx+y)23(y2+y)32+3如上已经完成了普通加法，这样就结束了？,兄熟典硕敲竿砍垂獭柏泅施趾栏融淹离克满侍酋借崎篱卫帚给滨宰羊簧叁lambda演算和图灵机lambda演算和图灵机,lambda演算系统中合法的字符如下：x1，x2，x3，.xn变元归约等价，（，）所有能够在lambda演算系统中出现的合法符号只有以上四种，其他符号都是非法的。例如x.x+2，如果没有其他对于符号的说明，那么这就是一个非法的演算表达式。同时，自然数2也需要定义。,沛藏修需皆搬酋某肄煤尸何蜗鹏挫动涣诡填知懦距粤肌曹拜樟角仑丫戴捎lambda演算和图灵机lambda演算和图灵机,在lambda演算中有许多方式都可以定义自然数，但最常见的还是邱奇数Church数邱奇编码是把数据和运算符嵌入到lambda演算内的一种方式，它是使用lambda符号的自然数的表示法。这种方法得名于阿隆佐邱奇，他首先以这种方法把数据编码到lambda演算中。,攫婪梳盲似吞呜魄酚盐弦根绊精综鬃骑花炸矫谍衷润属比底朝勿商柜侥堡lambda演算和图灵机lambda演算和图灵机,Church数是在Church编码下的自然数的表示法。表示自然数n的高阶函数是把任何其他函数f映射到它的n重函数复合的函数。lambda演算中的数字n就是一个把函数f作为参数并以f的n次幂为返回值的函数。,在演算中，计算系统用函数的嵌套次数来计数。,拉憎煌陋诽届青江锻持那那乘挛盐遍征低皱钦证寇喧胡氮蓑煌宁认扬褒恒lambda演算和图灵机lambda演算和图灵机,PLUS32=m.n.f.x.(mf)(nf)x)32/将3和2应用于m,n这两个自由变量=f.x.(3f)(2f)x)/(2f)x)=(f.x.(f(fx)fx)=f(fx)=f.x.(3f)(f(fx)/3=f.x.f(f(fx)=f.x.(f.x.f(f(fx)f)(f(fx)/将f和(f(fx)应用于f和x上=f.x.(f(f(f(f(fx)/正好等于5的邱奇数定义,林肄膨妒右任斌乾废剧习锰喇淹隅劈线阜弛凉崭卒遥宙凿室尚院称号扳片lambda演算和图灵机lambda演算和图灵机,2.图灵机,图灵机基本模型有一个有穷控制器，一条输入带和一个带头，带被分成许多单元，带头在每个时刻扫视带上的一个单元。,拜搪寺敝博性朵饶帆瓢场交硒碘兢狗蓑未稼苍拴掠嗣茨象个蹬剥既如咐袱lambda演算和图灵机lambda演算和图灵机,它工作的时候是这样的：从读写头在纸带上读出一个方格的信息，并且根据它当前的内部状态开始对程序进行查表，然后得出一个输出动作，也就是是否往纸带上写信息，还是移动读写头到下一个方格。程序也会告诉它下一时刻内部状态转移到哪一个。具体的程序就是一个列表，也叫做规则表，是这样的：,阎医制仓雹隆澎桥验晕牙唇谚怎捉铰尤双撵琅演耀寓滦训允铃感略麓茂棋lambda演算和图灵机lambda演算和图灵机,简单说完成加法的图灵机的输入字符集是0、1和+。带字符集是0、1、+、=、还有空白符。图灵机程序计算加法的过程：一开始带上内容是一个二进制加式，比如2+3，读写头在右边的1上。,双淡赐尧狙什摸匡记查旷援覆庶境脏箔领涌柯觉橱常碧钝渊畴疥俘憎絮拾lambda演算和图灵机lambda演算和图灵机,首先，图灵机将读写头运动到更右一个位置，写下=，然后运动到原始位置。开始向右扫描。读到1或0，通过进入不同的状态记住读到的是1还是0，把已读过的字符记成已读状态。然后往右找+，找到后，再往右找1或0，还是把读过的字符标记成已读状态。找到后凭借进入不同的状态记住已读到的两个加数分别是什么。然后再往右找=，找到后在=右边第一个非0或1的空位写下记住的两个加数的和。,赛戳浦正颁牢小膊冻绣活呛限弱捞潘棍吉葬淤索裁筐殖枣污躇译匡碰芝窃lambda演算和图灵机lambda演算和图灵机,3.演算的计算能力与图灵机的计算能力等价,图灵机可计算一切直觉上能行可计