前言
上个月月末的时候，看了《The Little Schemer》的第九章，第九章就是在讲停机问题和Y组合子。感觉很有意思，Y组合子真的是一个很神奇又有趣的东西，以至于MIT数学系的系徽就用的是Y组合子。Y组合子的发现者Haskell B.Curry把Y组合子纹在手臂上，他觉得自己捡了个大便宜。什么？你不知道这个人？我也不知道，但是学编程的Haskell这个单词应该很眼熟吧，没错就是用这个人的名字命名的Haskell语言。可见此人必定是大魔法师啊，魔法师，你懂得。手臂上封印Y组合子，手中莫名的多了汽油和火把。
其实我也是魔法师这个高贵职业中得一员，Lv.22即将升到Lv.23。
MIT数学系系徽
停机问题
首先是停机问题，我们来思考这样一个问题：是否会有这样一个程序告诉我们一个函数对于它的每一个输入都能够返回一个值？什么意思？看我们的题目，停机问题啊，一个程序返回了那就是停机了，如果一直运行下去，那就是不停机。什么没见过一直运行下去的程序？去写个函数，无参，自己调自己你看它能返回不？好，现在停机的概念已经清楚了，那么我们问题是什么？就是说会不会有这么一个程序，我们传入另一个程序，它返回true或false，如果是true，那就是说这个程序停机，如果是false那就是说这个程序不停机，问题清楚了吧。所以有还是没有呢？好，我知道你们都会说没有，但是我还是要刚一波，我就说有。假如有应该是这个样子，参数是一个函数f，返回值应该是true或者false。我们用Scheme来定义一下这个充满魔法自带火把的函数：
(define will-stop?
(lambda (f)
...))
在这里简单的说一下Scheme的语法：
define就是起个名，函数的定义：很简单，lambda关键字，括号里面是参数表，然后是函数体，就是下面的样子。
(define add
(lambda (x y)
(+ x y)))
(define <fun-name>
(lambda (<args>)
<body>))
函数的调用：就是先写操作符，然后写实参，实际上就是前缀表达式。写法就像下面的样子：
(+ 1 2)
((lambda (x y)
(+ x y)) 1 2)
(<op> <args>)
这里必须吹一波Scheme语法，简洁到令人感动。Lisp语言诞生于1958年，至今还很活跃，如运行在JVM上的Clojure，我感觉语法有很大的功劳。那些号称语法简洁的语言如某Go，看了看，感觉也就那样。
吹B结束，回到我们之前的问题，现在我们这个will-stop?函数已经写好了。好我们写两个函数验验货，先写一个可以停机的吧。
(define length
(lambda (l)
(cond
((null? l) 0)
(else
(+ 1 (length (cdr l)))))))
这个函数接受一个list作为参数，就是数据结构中的链表。然后呢如果是空链表就返回0，否则的话返回(+ 1 (length (cdr l)))，cdr就是除去链表第一个元素形成的新的链表。所以这个函数是对的吧，传入一个list，返回它的元素个数也就是节点的个数，这个值就是list的长度。就像Java中List的size方法一样。显然对于一个合法的参数，length函数是可以停机的。什么你说无穷流？我认为它不合法:）。现在我们将length传给will-stop?，它就会返回true。现在再来想一个不会停机的函数，这个简单，递归啊！看下面的函数，以x为参数，然后函数中再用自己去调用x，这样它就会一直的运行下去。所以(will-stop? eternity)会返回false。好，现在我们充满魔法的的will-stop？函数已经可以工作了。说了这么多，其实就是假设我们有这样的程序，反证法么，上学的时候证明题做不出来就反证啊！
(define eternity
(lambda (x)
(eternity x)))
现在我们利用现有的will-stop?函数来写另一个函数：
(define last-try
(lambda ()
(and (will-stop? last-try)
(eternity '())))
这里说一下Scheme中的and，如果第一个表达式返回false，就返回false。如果前面的的表达式都返回的true，就返回最后一个表达式。所以看一下last-try这个函数，无参数，函数体的意思是，如果last-try停机我就调用eternity函数，如果last-try不停机我就返回false。
没错吧？是这个意思吧，好记住！
有没有发现哪里不对？我们调用一下(will-stop? last-try)，完了，崩了！我们充满魔法的will-stop?总会给我们一个答案，如果是true，那么我们认为last-try是可以停机的。但是我们上面有说过，last-try函数如果停机，就会调用eternity函数，就不会停机。如果是不可停机的，即(will-stop? last-try)返回的是false，也就是说充满魔法的程序告诉我们last-try是不会停机的。但是我们就看last-try的函数体，如果last-try不停机，就直接返回false，停机了。。。
Ok！矛盾了，所以说不存在这样一个程序。原来写不出来是因为不存在，不是我们不够牛逼，心里这就好受多了，感谢图灵和哥德尔，66666！
好，停机问题到此结束，先用这个简单的问题来醒醒脑。
下集预告
第二篇文章会用Scheme语言一步一步的推倒出Y Combinator，敬请期待:）。
还得说一嘴，网上总有人说一下午看完了Dan的《The Little Schemer》，这帮人真的挺low的。这书虽然写的像个小人书一样，而且也就两百来页，但是进入第八章之后，瞬间高能！一下午都不见得看得完一章，你要说你一下午看完了《Thinking in Java》，那我信:）。人越缺少什么就越爱炫耀什么，骨子里还是自卑的。所以总是向别人炫耀自己多么聪明的，对吧:）。
网友评论