• 具体的程序就是一个列表，也叫做规则表，是这样的：
当前内部状态s 输入数值i 输出动作o 下一时刻的内部状态s'
q0 q1
1 0
前移 往纸带上写
q1 qn
q2
0
后移
qy
• 简单说完成加法的图灵机的输入字符集是0、1和+。带 字符集是0、1、+、=、还有空白符。 • 图灵机程序计算加法的过程： 一开始带上内容是一个二进制加式，比如2+3，读写头 在右边的 1 上。
2.图灵机
• 图灵机基本模型有一个有穷控制器，一条输入带和一个带 头，带被分成许多单元，带头在每个时刻扫视带上的一个 单元。
• 它工作的时候是这样的：从读写头在纸带上读出一个方 格的信息，并且根据它当前的内部状态开始对程序进行 查表，然后得出一个输出动作，也就是是否往纸带上写 信息，还是移动读写头到下一个方格。程序也会告诉它 下一时刻内部状态转移到哪一个。
3.λ演算的计算能力与图灵机的计算能力等价
• 图灵机可计算一切直觉上能行可计算的函数。 • λ演算之通用在于，任何一个可计算函数都能用这种形式 来表达和求值。 • 因而，λ演算的计算能力是等价于图灵机的。
在λ演算中，计算系统 用函数的嵌套次数来计数。
• lambda演算中的数字n就是一个把函数 f 作为参数并以 f 的n次幂为返回值.λf.λx.( (m f)((n f) x) ) 3 2 //将3和2应用于m,n这两个自由变量 =λf.λx.( (3 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)) 应用于f和x上 =λf.λx.(f (f (f (f (f x))))) //正好等于5的邱奇数定义
λ表达式的唯一形式：x，λy•e，f(a) 例如：f(x,y)=x+y λx•λy•x+y 函数求值： f(2,3)可以表示为： (λx•λy•x+y) 2 3 (λy•2+y)3 2+3 如上已经完成了普通加法，这样就结束了？？
lambda演算系统中合法的字符如下： • x1，x2，x3，...xn 变元 • →归约 • ＝ 等价 • λ，（，） 所有能够在lambda演算系统中出现的合法符号只有以上四 种，其他符号都是非法的。例如λx.x+2，如果没有其他对 于＋符号的说明，那么这就是一个非法的λ演算表达式。 同时，自然数 2 也需要定义。
b
b
1
0
+
1
1
=
b
• 首先，图灵机将读写头运动到更右一个位置，写下 =，然 后运动到原始位置。 • 开始向右扫描。读到 1 或 0，通过进入不同的状态记住读 到的是 1 还是 0，把已读过的字符记成已读状态。 • 然后往右找 + ，找到后，再往右找 1 或 0，还是把读过的 字符标记成已读状态。找到后凭借进入不同的状态记住已 读到的两个加数分别是什么。 • 然后再往右找 =，找到后在 = 右边第一个非 0 或 1 的空 位写下记住的两个加数的和。
软件工程理论报告
报告内容
• 使用λ演算的计算和图灵机模型完成简单的加法运算。 • 说明λ演算的计算能力与图灵机的计算能力等价。
1.λ演算
• λ演算（lambda calculus）是一套用于研究函数定义、函 数应用和递归的形式系统。它由阿隆佐·邱奇和他的学生斯 蒂芬·科尔·克莱尼在20世纪30年代发明的。 • λ演算可以被称为最小的通用程序设计语言。它包括一条 变换规则（变量替换）和一条函数定义方式。 • λ演算表达了两个计算机计算中最基本的概念“代入”和 “置换”。“代入”我们一般理解为函数调用，或者是用 实参代替函数中的形参；“置换”我们一般理解为变量换 名规则。“代入”就是用lambda演算中的β-归约概念。而 “替换”就是lambda演算中的α-变换。
• 在 lambda 演算中有许多方式都可以定义自然数，但最常 见的还是邱奇数 • Church数 邱奇编码是把数据和运算符嵌入到lambda演算内的一种方 式，它是使用lambda符号的自然数的表示法。这种方法 得名于阿隆佐·邱奇，他首先以这种方法把数据编码到 lambda演算中。
• Church数是在Church编码下的自然数的表示法。表示自 然数n的高阶函数是把任何其他函数 f 映射到它的n重函数 复合 的函数。