Lambda表达式与图灵完备

Posted on Edited on Word count in article: 3.4k Reading time ≈ 3 mins.

引子

这篇还是用中文写吧。我基本上没有看到中文的推导过程。当然英文的也各种缺失推导过程。有空的话再用英文写一篇（我肯定没有空）。

首先是lambda表达式。用过Python, Java, JS的，都应该知道。否则意味着你肯定没有好好学。

我是从国外的视频中看到lambda表达式和图灵机等价这一观点的。然后人家就进行了简单的推导。然而我根本就看不懂。我很怀疑我的英语水平，于是又仔细看了几遍视频，仍然不懂。我觉得我需要研究一下，因为视频中的很多推导都明白了。但是就有一步推导，讲解者说了这过程比较复杂，然后就带过了。我非常想知道这推导过程怎么来的。所以搜索了许多资料，加上自己的思考，写了下面的文字。

图灵完备

图灵完备是个什么意思？通俗的意思就是能实现正整数加减法，if判断跳转，while循环，以及可以构造简单数据结构的都称为图灵完备。图灵完备的语言无法处理停机问题。具备图灵完备的假象机器就是图灵机。你认为正整数加减法，if判断跳转，while循环很简单，所以你这个人也是图灵机的一种。

所有编程语言都会将图灵完备作为最基础的目标。你看比特币智能合约这么火，它也说自己是图灵完备的。这样看来图灵完备是检测这门编程语言是否能通用的前提。当然Java、Python、JS等等都是图灵完备的。

lambda表达式

在推导之前先看看什么是lambda表达式。

1
2
f(x) -> x
f(x,y) -> x

我认为以上都是lambda表达式。其中f,x都是变量，不光可以代表值还可以代表函数。f(x)代表一次f对x的调用。-> 是说最终得到x, 或者结果为x.

lambda表达式图灵完备推导

下面开始推导，首先的前提条件是赋值和等价这两个操作是最初存在的。为什么要提这个事情呢？因为不提这个事情就无法进行if的判断，也没有办法得到结果。其实图灵机的定义中其实也暗含了赋值和等价判断这两个基础操作。所有人都认为理所当然，只有我特意将这两个操作提出来。

推导之前我们必须有的基础操作

  • 赋值
  • 判断等价
  • 调用，使用**()表示，也可以使用.**表示

另外我们还应该清楚一件事，就是单参lambda完全等价于多参lambda表达式。在最初的1920+年Church这伟大的人物提出来lambda的时候就是使用的单参。但是我们为了推导方便，我故意使用多参。

问题: 多参为什么等价于单参lambda?

答:

1
2
3
4
5
f(x,y) -> z
t -> (x,y) 这里的括号无二义的时候可以去掉，就是 t -> x,y

所以 f(t) -> z
证毕

下面开始真正的推导：

首先定义True与False

1
2
False: x -> x  , 这样写你是不是更明白? (f,x) -> x
True: f,x -> f  这样写你是不是更明白?  (f,x) -> f

然后就可以定义IF判断了。你看看False的定义是不是就是False ? f : x. True的定义是不是True ? f : x.所以False返回了x,而True返回f.我们将IF定义为多元组

1
2
3
4
5
6
IF(False,f,x) -> x
IF(True, f,x) -> f
同时认为
Fst(f,x) -> f 等同于IF(True,f,x)
Snd(f,x) -> x 等同于IF(False,f,x)
这其实就是投影操作。

下面我们再来定义正整数。False在我们计算机界经常被认为是0.所以我们0的定义就是

1
0: f,x -> x

正整数1的定义，我们认为调用了一次f,即

1
1: f,x -> f(x)

下面正整数2，3…，n的定义就是

1
2
3
4
2: f,x -> f(f(x))
3: f,x -> f(f(f(x)))
...
n: f,x -> f(f(...f(x)...)) 这里应有有n个f调用

我们下面为了更加方便我们这样简写：

1
2
3
4
2: f,x -> 2.f(x)
3: f,x -> 3.f(x)
...
n: f,x -> n.f(x)

我们下面来定义加法操作。例如n + m. 这个问题不好想，所以先想特例。例如5 = 2 + 3, 那么怎么得到5呢，就是5次函数调用：

1
2
3
5: f,x -> f(f(f(f(f(x))))) == f(f(f(2.f(x)))) == 3.f(m) == 3.f(2.f(x))  其中2.f(x) 替换成m，然后再替换回来。
替换一下
n+m: f,x -> n.f(m.f(x))

定义下乘法操作.例如n*m. 同样先想特例： 6 = 3 * 2. 怎么得到6呢?

1
6: f,x -> f(f(f(f(f(f(x)))))) == 2.f(2.f(2.f(x))) == 3.2.f(x)  其中2.f(x)替换为z所以就变成了3.z(x) 再替换回来就是3.2.f(x)

下面是定义n++操作，这个在数学上叫做Successor,所以我叫这个lambda为Succ. 其实从n到n+1是很简单。

1
2
Succ: n,f,x -> f(n.f(x))  就是多调一次f就行了

下面是定义n–操作，这个在数学上叫做Predecessor. 这个是最复杂的。我看视频就是没看懂这里。问题是怎么从n变成n-1。我知道n-1怎么变成n。那有没有方法将n-1带入公式，最后再同时消除呢？就这么干！当年Church可是苦想n天。我辈比较幸运，直接知道人家的想法了。看这篇文章的你们就更加幸运，因为我把所有被省略的推理过程也写出来了。

1
2
3
4
5
6
7
8
9
先定义： PSucc(n) -> (Snd n,Succ(Snd n))
那么PSucc((0,0)) -> (0,1)
那么我们对PSucc(0)做n次操作就是
n.PSucc((0,0)) = PSucc(PSucc(...PSucc((0,1))...)) 记住这里只有n-1个PSucc调用，因为其中一个PSucc((0,0))已经变成了(0,1)了
               = (n-1, n)

那我们定义
Pred(n) -> Fst n.PSucc((0,0)) = n-1
Pred就是Predecessor

现在好办了，只要有了加减法，所有的一切操作就都好办了。

1
2
n-m的减法就是执行n--操作m次。
SUB(n,m) -> m.Pred(n)

下面再定义一些AND,OR,NOT就非常简单了

1
2
3
AND(a,b) -> IF(a,b,False) 这个意思就是如果a是真的，那就看b是不是真的。否则，那一定返回False.
OR(a,b) -> IF(a,True,b) 
NOT(a) -> IF(a,False,True)

下面再定义while循环

1
WHILE(n,f) -> n.f

再来定义点简单的数据结构，例如链表, 这里还是学习了一下Lisp

1
2
3
4
5
6
7
8
9
> (cons 1 2)
> x
(1 . 2 )
这创建了一个头是1，尾是2的cons对象。
对cons的操作有两个，car及cdr，分别是读取cons的头和尾元素：
> (car (cons 1 2))
1
> (cdr (cons 1 2))
2

cons代表的是构建一个链表。 car代表是前一个节点，cdr代表的是后一个节点。那么我们用lambda表达式也写一个。

1
2
3
构造链表cons: cons(a,b) -> (a,b)
获取前一个节点car: car(a,b) -> a
获取后一个节点cdr: cdr(a,b) -> b

我们将0判断、False判断、null判断这三种操作认为是等价的。文章开始也说了，等价判断是先决条件。所以0判断一定是预先存在的。所以lambda表达式图灵完备了。

再说一点，图灵完备，意味着无法停机。停机证明不是本文的重点，不再证明。(对对对，就是笔者不会证明。你们随便吐槽)

总结

看了这篇文章你能学习到什么？你能证明1+2 == 3 ？还是会写链表了？lambda证明到底有什么用？根本就没有编程来的实在！你说的太对了。我也这样认为。那这篇文章到底有什么用？

就是为了装逼呀!!!

你看blockchain智能合约这么火，最后还不忘加上图灵完备字样。为啥？为了装逼呀~~~学计算机的这么多人，懂得图灵完备没有几个，懂得怎么证明图灵完备估计也没有几个。以后你们大可以吹嘘自己知道如何证明图灵完备。

看到一条微博，说：“太难了，我大脑停机了。” 就回复：“你竟然不是图灵完备的!!”

以后有谁再说**“我无法思考了”**,你们就接话：“你竟然不是图灵完备的!!”

对，以后谁在你们面前装逼说自己会图灵完备的证明，你们就接话：“我也会!!”

这才是这篇文章的正确打开方式。