微博

侯世达在他著名的《集异璧》中提出的WU谜题，是关于用三个字母W,I和U组成的字符串的题目。

对于任何一个由W,I和U组成的字符串，允许通过以下四条规则来将其变换到另一个字符串：
1. xI -> xIU
也即：如果目前字符串以I结尾，则可在结尾处再加一个U。比如WI可以变换为WIU
2. Wx -> Wxx
也即：如果目前字符串以W开头，则可以把W后的子字符串再重复一遍。比如WIU可以变为WIUIU
3. xIIIy -> xUy
也即：如果目前字符串中无论哪个位置有三个连在一起的I，那么可用一个U来取代。比如WUIIIU可变换为WUUU
4. xUUy -> xy
也即：如果目前字符串中无论哪个位置有两个连在一起的U，那么可以将其删去。比如WUUU可变换为WU

问：通过反复使用以上规则，有无可能在有限次内将WI变成WU？

答：无可能。因为如果某个字符串中I的个数不能被3整除，则通过四条规则中任何一条变换后的字符串中I的个数仍不能被3整除。WI中的I个数不能被3整除，而WU中的I的个数（0个）可被3整除。

这个谜题为什么有名？因为通过它可以理解两个关于数学（形式）证明的关键点，从而理解哥德尔不完全性定理。

=============

1） 一个数学形式系统中的一个数学证明，它其实和WU谜题一样，就是从某些字符串（公理）出发，通过固定的规则，把一个字符串变换成另一个字符串的过程。这是一个只和语法有关，和语义无关的过程，至少从形式上来看是这样的。

一个这样的证明是可以被电脑程序验证的。电脑程序无须理解这个证明是在讲什么，而只须验证字符串的变换过程的确符合规则，而且证明中的字符串要么是公理，要么是已经通过规则变换出来的字符串，而最后那个字符串就是我们要证的命题，这个证明就是成立的。这样的证明叫形式证明。

许多数学形式系统中有许多的公理，但固定的变换规则，可以简单到只有肯定前件式一条，拉丁文称为Modus ponens，也即“如果能变换出字符串P->Q，也能变换出字符串P，那么就允许变换出字符串Q”（其实就是“如果P则Q，现在P，所以Q”的推理规则，但是在这里我们要把它仅仅看作是关于字符串的变换规则）。

实际的数学活动中的绝大多数数学家，写出来的证明当然不会真是一些字符串的变换。这些的证明中充满了需要对语义的了解才能理解的东西，往往步骤之间跳跃很大，没有此领域的专业知识无法理解。但是绝大多数数学家都会承认，如果补充得足够详细的话，他们的证明，至少从原则上说，都是能够成为形式证明的。

所以“在某个给定的数学形式系统中，某命题可以（或不可以）被证明”这个问题，就是一个类似WU谜题的问题：“从某些的字符串出发，通过某些变换规则，能不能变换出某个字符串来？”

------

哥德尔的两个不完全性定理，从上面这个角度理解，其实就是关于字符串变换的定理。比如哥德尔第一不完全性定理其实是在说，一个包含了一阶算术的（自洽的）形式公理系统（这是一个关于字符串变换的系统，从这方面讲，它和WU谜题并无不同），总可以从中找到一个字符串G，你既变换不出G这个字符串来，也变换不出¬字符后再跟着G的这个字符串来。

=============

2） 让我们把WU谜题改写一下。

对于任何一个自然数n开始，允许通过以下四条规则来将其变换到另一个自然数：
1. 如果n能被10整除，则可将其变换为10n+1，
2. 如果n=2*10^k+p，其中k>=1，p<10^k，那么可将其变换为2*10^(2k)+p*10^k+p
3. 如果n=x*10^k+y，其中k>3，y<10^(k-3)，那么可将其变换为x*10^(k-2)+10^(k-3)+y
4. 如果n=x*10^k+11*10^(k-2)+y，其中k>2，y<10^(k-2)，那么可将其变换为x*10^(k-2)+y
问：通过反复使用以上规则，有无可能在有限次内将20变成21？

容易看出，这其实就是WU谜题，只不过W变成了2，I变成了0，U变成了1。

这个题目的形式，和著名的3x+1问题类似。3x+1问题是说，从任意一个自然数出发，通过两个规则：
1）如果n是偶数，则可将其变为n/2
2)如果n是奇数，则可将其变为3n+1
问：是否总是会掉进4->2->1的循环中。3x+1问题至今无人能解答。

改写过的WU谜题和3x+1问题一样，是一个算术命题。

-------

“在某个数学形式系统中，某命题可以（或不可以）被证明”这个问题，既然它和WU谜题一样，是在问：“从某些的字符串出发，通过某些变换规则，能不能变换出某个字符串来？”，于是它同样可以被改写成算术命题，尽管这个改写过程比WU谜题的改写复杂多了。

=============

简而言之：数学证明就是字符串的变换，要证明某某命题是证或证不出来的，就是证明某某字符串是变换得出或不出来的；而这些都能变成算术命题，要证明某某命题是证或证不出来的，只须证明某个算术命题是对还是错。

两个哥德尔不完全性定理讨论的是包含了算术系统的数学系统，这样的系统可以谈论算术命题，所以它从这种意义上就可以谈论它自己能不能证出什么来。