第一章

WU谜题

形式系统

本书中心的概念之一是形式系统。我用的这种形式系统是美国逻辑学家艾米尔·波斯特在二十世纪二十年代发明的，通常被称为“波斯特产生式系统”。本章将向读者介绍一个形式系统，并且我希望读者愿意——至少是有一点点愿意——去探索这个形式系统。为唤起读者的好奇心，我设计了一个小小的谜题。

这个谜题就是“你能产生WU吗？”。一开始的时候，我提供给你一个符号串（即一串字母）。为了解除你的悬念，可以告诉你那个符号串就是WJ。然后，你会得知一些规则，运用这些规则你可以将一个符号串变成另一个。如果某条规则在某处是适用的，并且你也愿意用它，你就可以用。但是，如果同时有几条可以适用的规则，又没有什么指导来说明你该用哪一条，这将留给你去选择。正是这一点使得做形式系统游戏成为一种技巧。重要的、几乎用不着说明的一点是，你决不能做任何背离规则的事情。我们也许可以把这个限制称做“形式化要求”。在本章中，这一点也许根本无需强调。但是我预言——这说起来挺怪的——当你在下面的章节中与形式系统周旋时，你会发现，你将一次又一次地违反形式化要求，除非你以前用过形式系统。

关于我们的形式系统——WJU系统——要说的第一件事是它只用了三个字母：W、J、U。就是说WJU系统的所有符号串都是由这三个字母组成的。以下是WJU系统的一些符号串。

WU

UJW

WUUWUU

UJJUWJUUJWUJJUWJUUJWUJJU

虽然所有这些符号串都是合法的，但它们还不算“归你所有”。事实上，到现在为止归你所有的符号串只有WJ。要增加你自己的储备，只能靠使用规则，我们现在就介绍这些规则。下面是第一条规则：

规则Ⅰ：如果一个归你所有的符号串结尾是J，则可以在其后面再加上一个U。

这里顺便指出一个事实（假如你到目前还未猜出“符号串”的意思）：符号串中的字母是有固定顺序的。比如WJ和JW是两个不同的符号串。一个符号串不是其字母的顺序无关紧要的“一堆符号”。