趣题：量子计算机、另类编程语言和幂函数的解释

很久没有更新和信息学有关的东西了。今天和大家分享一个非常有趣的题目，我已经很久没看见如此精彩有趣的题目了。为了引入这个问题，我们先来介绍一个假想的编程语言QCPL。就像LISP一样，它是一个基于函数的语言：没有变量，没有for循环，一切东西都是用函数来表示的。另外，就像FORTRAN一样，QCPL语言不支持递归，也就是说一个函数不能递归地调用自己。QCPL的另一个有趣的特点是，所有的函数都只能返回一个Boolean值。比如说，下面这个函数的作用就是判断x+2和y+2的乘积是否等于z：

MULT_PLUS_TWO(x,y,z): (x+2)*(y+2)=z

QCPL也有逻辑运算符。事实上，QCPL里的合法运算符一共只有8个，其中6个分别如下：

运算符 |  作用  |     输入      |     输出
——-+——–+—————+—————
  +    |  相加  |  两个自然数   |  一个自然数
  *    |  相乘  |  两个自然数   |  一个自然数
  =    |  等于  |  两个自然数   | 一个Boolean值
  &    | 逻辑和 | 两个Boolean值 | 一个Boolean值
  |    | 逻辑或 | 两个Boolean值 | 一个Boolean值
  !    | 逻辑非 | 一个Boolean值 | 一个Boolean值

另外两个运算符就要重点介绍了。这是QCPL语言真正牛B的地方——它是专门为量子计算机设计的！你可以让这台计算机平行地穷尽完某些变量所有可能的取值，这一切仅仅在一瞬间内就可以完成。这两个特殊的运算符（以后我们管它们叫做“定量运算符”）就是专门用来干这件牛B事的："Ex"是“存在性定量运算符”，表示让计算机找出是否存在一个满足表达式的自然数x；"Ax"是“通用性定量运算符”，用于询问计算机该表达式是否对所有的自然数x均成立。比如，运用定量运算符，我们可以立即写出素数/合数判断函数：

COMPOSITE(n): Ex,Ey,MULT_PLUS_TWO(x,y,n)
PRIME(n): !(COMPOSITE(n)|n=0|n=1)

其中，Ex,Ey,MULT_PLUS_TWO(x,y,n)的意思就是说，是否存在某一对x和y，使得MULT_PLUS_TWO(x,y,n)为真。只要（某一个平行世界里的）计算机找到了任何一对满足条件的x和y，整个COMPOSITE(n)立即返回True。如果对于所有的自然数x和y，MULT_PLUS_TWO(x,y,n)都不可能为真时，整个函数才返回False。别忘了这是一台量子计算机，穷举的过程可以在一瞬间内完成。

好了，下面我们再给出几个基本的函数。函数SUM用于计算x加y是否等于z，而函数PRODUCT则用于检验x乘以y是否等于z：

SUM(x,y,z): x+y=z
PRODUCT(x,y,z): x*y=z

现在，你的任务就是写出一个函数POWER(x,y,z)，当且仅当x的y次方等于z时函数才返回True。相信我，这道题没有那么容易。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝华丽的分割线＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

这真的是一道难题。你必须要跳出常规的编程思路，找出与这种全新的编程语言相符的“算法”。这里是没有循环结构的，但它有一个更牛B的东西，它可以在一瞬间穷举所有可能的变量。也就是说，交给这台计算机的问题最好都是“是否存在一个什么什么，使得某某东西成立”的形式。把我们的题目“翻译”过去，就是：是否存在一个数列{A_n}，满足A_0=1，且对i>0都有A_i=A_(i-1)*x，并且数列中的A_y项恰好等于z？注意到QCPL里面只有加法和乘法，因此我们不得不借用数列的概念来描述x的幂。可惜的是QCPL语言又不支持数列结构，因此我们不得不把整个数列“编码”成一个数。最简单的编码方式就是使用n进制储存数列中的所有数，其中n要比所有的A_i都要大。现在问题又来了，我们如何从这个已经编码的数列中“提取”指定位置上的数？想了半天想不出办法，我们突然想到，为什么不把数列本身的序号也带进这个数列中？这样我们可以用一个存在性定量运算符来确定我们需要的数所在的位置。这样，我们可以把有序数对(x^i,i)作为数列的元素，则问题转换为检查数列中是否存在(z,y)一项。而每个有序数对(a,b)也同样可以用类似地方法进行编码：选取一个大于所有b的数m，则数对(a,b)和数a*m+b一一对应。

好了，让我们重新整理一下我们的思路。我们需要让计算机寻找一个数列，数列的元素是一个个有序数对，其中第一个元素是(1,0)，最后一个元素是(z,y)，并且(A_i, B_i)总是等于(A_(i-1) * x, B_(i-1) + 1)。为了把数列转换为QCPL可以接受的形式，我们选取一个大于y的数m，把数对(a,b)转化为a*m+b；再选取一个不小于(z+1)*(y+1)的数n，把数列转化为一个n进制的数。这样最终编码出的结果应该是Σn^i*(A_i*m+B_i)。

(a,b)与a*m+b之间的转换需要用到函数DIVMOD，它用于计算n除以m的商和余数是否为a,b，定义为：

DIVMOD(n,m,a,b): LT(b,m)&(n=m*a+b)

其中，LT(b,m)返回True当且仅当b<m。这些比较函数可以用下面的方式定义出来。

LE(a,b): Ex, a+x=b  /* a<=b */
GE(a,b): LE(b,a)    /* a>=b */
LT(a,b): !GE(a,b)   /* a<b */
GT(a,b): !LE(a,b)   /* a>b */
NE(a,b): !(a=b)     /* a≠b */

下面这个函数用于提取一个n进制数的某一位上的数字，其中参数a表示整个数列编码后的数，n表示编码所用的基数，参数v的值应为n^i，函数返回数列中的第i个数是否为x。这个x应该等于a除以v的商，再除以n的余数。这个函数定义为：

ELEMENT(a,n,v,x): Er,Ey,Eq,DIVMOD(a,v,r,y)&DIVMOD(r,n,q,x)

为了更好的理解这个函数，考虑一个十进制数12345，显然有：

12345 ÷ 100 = 123 … 45

123 ÷ 10 = 12 … 3

最后的余数3就是我们想要提取出来的数。上面的例子中，100就是那个v，123和45分别是r和y，12和3分别是q和x。

但要想判断v的值是否等于n^i，问题似乎又回到了起始点。不过，不同的是，现在再来判断v=n^i要简单多了，因为我们不需要指定指数i的值（数的位置可以从数列本身中获知），并且我们可以任意取一个自己觉得用着方便的底数n。事实上，当n为一个质数p时，判断x是否为p的幂非常简单：

PRIMEPOWER(p,x): (x=1)|Aa,Ab,(!(a*b=x))|(!PRIME(a))|(p=a)

这个函数的基本思路就是，如果p是一个质数，而x是p的幂，那么p是x的唯一一个质因子。也就是说，对于任何一个自然数a，要么它等于p，要么它不是一个质数，否则的话a*b就不可能等于x。函数用到了我们题目中引入的PRIME函数。

一切准备就绪了。下面我们需要分别写出数列的三个约束条件。首先，我们需要保证数列以(1,0)开头，即编码之后的p进制数a

的最低位上的数字为m，也即a除以p的余数为m。于是，第一个条件可以写作：

CONDITION_ONE(a,p,m): Er,DIVMOD(a,p,r,m)

接下来，我们希望数列以(z,y)结尾，即a的最高位是m*z+y。换句话说，a除以某个p的幂后，得到的商正好等于m*z+y。于是，我们把条件二写成：

CONDITION_TWO(a,p,m,z,y): Ev,Er,En,PRIMEPOWER(p,v) & DIVMOD(a,v,n,r) & DIVMOD(n,m,z,y)

最后，我们需要保证这个数列中（除最后一项外）的每一项都与它的下一个数对有“乘以x”和“加1”的递推关系。这个条件可以写成：

CONDITION_THREE(a,p,m,x):
Av,(!PRIMEPOWER(p,v)) |  GT(v*p,a) |    /* ignoring the last element of a */
(Ed,Ee,Eq,Er,Es,Et, ELEMENT(a,p,v,d) & ELEMENT(a,p,v*p,e) & DIVMOD(d,m,q,r) & DIVMOD(e,m,s,t) & (q*x=s) & (r+1=t))

最后，我们只需要把这三个约束条件结合起来，询问计算机是否存在同时满足这三个条件的序列a。我们最终的POWER函数为：

POWER(x,y,z):
(!((x=0)&(y=0))) & /* avoiding 0^0 */
Ea, /* a is our "proof" sequence */
Ep, /* p is the prime used in decoding a */
Em, /* m is used in decoding tuples within a */
GT(m,y) & PRIME(p) & GT(p,m*(z+1)) & CONDITION_ONE(a,p,m) & CONDITION_TWO(a,p,m,z,y) & CONDITION_THREE(a,p,m,x)

参考资料：http://www.brand.site.co.il/riddles/200801q.html