宇宙的零成本分裂

非确定性计算，就是科幻小说里的平行宇宙。反过来说更合理一些。不过，觉得一上来就说非确定性运算，很有气质……

Murphis 手里的红药丸与蓝药丸，Neo 选择了前者。这是单个宇宙里的计算。对于平行宇宙而言，当 Neo 选了红药丸的那一瞬间，宇宙分裂成了两个，在另一个宇宙里，Neo 选了蓝药丸。

在两个宇宙里的 Neo 选了不同颜色的药丸之后，他们接下来还要做更多的选择，就会导致宇宙不断分裂。倘若从 Neo 选择药丸的那一刻开始，结果会得到一棵根深叶茂的宇宙树。

以前我说过，只要有选择，这就意味着选择者已经落入了一个已经编制好的程序里了 [1]。既然是程序，那就得有运行结果，否则就是死循环。因此从根宇宙开始，向叶宇宙走，位于最长的路径末端的叶宇宙是笑到最后的宇宙，它可以作为这个程序的运行结果。这个叶宇宙，就是我们看过好几遍的《黑客帝国》。

这就是宇宙规模的非确定性计算。

由于我不相信我活在一个编制好的程序里，所以平行宇宙就的话题就此为止。不过，非确定性计算却是一个值得探究的话题。透彻地理解它，至少对于任何单机游戏的通关有帮助。因为基于非确定性运算，能够算出单机游戏通关的所有路径。有了这个技能，也可以在街头摆个摊，给那些认为自己生活在一个单机游戏里的人算算命。

为了更为直观且精确地表现非确定性计算，需要构造一个例子。先来看一个确定性的计算过程：

if (Neo 选了红药丸)
  《黑客帝国》
else
  导演不拍了

这个计算过程是，倘若 Neo 选了红药丸，我们就有《黑客帝国》可以看，否则导演没法拍，拍了也没人看。

现在，我们将计算过程倒过来，就是电影是一定要拍出来的，然后让 Neo 按照这个要求去选药丸：

if (Neo 从 (红药丸，蓝药丸) 作选择)
  《黑客帝国》
else
  导演不拍了

这样一来，对于 Neo 而言，他面临的就是一个非确定性计算的问题。他要解决这个问题，就只能让宇宙去分裂……我们不关心 Neo 如何选择，只要他作出的选择能够保证拍出《黑客帝国》这部电影即可。

倘若对续延 [2] 有所了解，现在想必在上述代码中已经看到了续延：

if ([])
  《黑客帝国》
else
  导演不拍了

续延里的洞是个黑洞。包含这种洞的代码结构会掉进这个洞里，再从洞里掉出来一个值。由于我们要求必须得拍出《黑客帝国》这部电影，因此从这个洞里掉出来的必须是《黑客帝国》。洞外之物决定了洞内的 Neo 的选择。倘若 Neo 选了蓝药丸，洞外之物决定了他的选择会导致导演不拍了，所以 Neo 就试着再选择红药丸，于是《黑客帝国》就拍出来了。

所以，黑洞未必真黑。外围的世界完全可以决定黑洞里面的事。为了展现这一点，我需要用 Scheme 语言重新描述上述过程：

(if ([])
    《黑客帝国》
    导演不拍了)

接下来，看一下洞里必须发生的事是什么：

(if ((call/cc
      (lambda (cc)
        (if ((cc '蓝药丸) 《黑客帝国》)
            《黑客帝国》
            (cc '红药丸)) 
        )))
    《黑客帝国》
    导演不拍了)

在介绍阴阳谜题 [3] 的时候，已经说过了 call/cc 的作用，它可以在表达式里挖一个黑洞，再在这个黑洞里布置一个函数来处理掉入洞中的东西。

在 call/cc 布置的黑洞里，Neo 必须对药丸们逐一进行选择，然后看看续延的求值结果是不是《黑客帝国》。这里由于只有两种选择，所以，黑洞里只需要用 if 语句就可以涵盖它们。

洞内发生的计算就是非确定性计算。虽然它在形式上与一开始的确定性计算没有本质上的不同，但是它却很好的模拟了「宇宙分裂」。很多人觉得随便一个人选择是吃米饭还是吃面条这种破事就让宇宙分裂一次，成本太高了。现在看到了吧，有了续延，这种事基本上是零成本的。

续延不仅降低了宇宙分裂的成本，而且它还能响应洞外的事件的变化。例如，现在要求 Neo 选择蓝药丸才能拍出《黑客帝国》，上述代码不用修改，依然可用。因为我们一开始就已经假设了，不管洞内发生了什么计算，反正得满足洞外的需求。

有了上述认识，接下来再去看 [4]，可能就不那么一头雾水了。

[1] 红药丸，还是蓝药丸
[2] 续延，有什么难的……
[3] 三生万物
[4] Scheme 里的非确定性运算