GEB - WU 谜题

《GEB》中的第一章,有这样一道题:

有一个 WJU 系统,由字符集为 W, J, U 的字符串组成。其中包含四条字符串变换规则(其中 x, y 表示任意合法字符串且可以为空):

  • xJ => xJU
  • Wx => Wxx
  • xJJJy => xUy
  • xUUy => xy

从 WJ 出发,能不能得到 WU?

推导如下:

令字符串的值 = J 的个数 + U 的个数 * 3,然后发现无论哪条规则都不改变字符串值对 3 取模的余数。所以 WJ 到 WU 的变换是不可能的。

题外话:书中没给证明,于是就写成博客了。书中介绍这道题只是为了介绍定理、公理、推导等概念。一般这种题可以先试图构造一番,发现不大行的时候转而试图证明无解,而证明无解的方法就是构造不变量。