Mathematica 强大的符号计算和化简能力相信会让不少人震撼不已。输入 Sum[1/n^2, {n, 1, ∞}] , Mathematica 竟然知道它等于 π^2/6 。我不禁问自己, Mathematica 真的什么都能化简出来吗?今天,我偶然遇到一个简单的表达式, Mathematica 竟然不知道它的精确值。
在 Mathematica 中输入 Cot[π/2] , Mathematica 会告诉你它等于 0 ;在 Mathematica 中输入 Cot[π/4] , Mathematica 会告诉你它等于 1 ;但在 Mathematica 中输入 Cot[π/8] , Mathematica 返回的却还是一个 Cot[π/8] ,并没有给出它的值。而 Cot[π/8] 并不是一个复杂到无法用四则运算和平方开方表达出来的数。在一个边长为 1 的正八边形中,每条边的所对应的“圆心角”为 2π/8 = π/4 ,因此“圆周角” α 就等于 π/8 。由下图我们可以轻易看出, Cot[π/8]=√2+1 。
哈哈!我大笑,原来 Mathematica 也有做不到的事情!于是,我查了查 Mathematica 的帮助文档,想看看 Mathematica 对这个问题有何说明。万万没有想到的是,其实 Mathematica 并不是不知道 Cot[π/8] 等于多少,只是智能地保留了 Cot[π/8] 的形式。如果你愿意的话,可以用 FunctionExpand 函数将其展开,得到 Cot[π/8] 的精确结果。
Mathematica 真有那么无敌吗?不妨继续拿三角函数考考 Mathematica ,试探出 Mathematica 的极限。由于正十七边形可以用尺规作图作出,因此 π/17 的三角函数值理论上说是可以表示出来的。而无所不知的 Mathematica 也再一次给出了我们期待的结果:
联想到正 65537 边形也能用尺规作图完成,这表明 π/65537 的三角函数值也能展开为用有限次加减乘除和平方开方构成的表达式。 Mathematica 还能算出 π/65537 的三角函数值吗?这下 Mathematica 似乎无能为力了。
由此可见, Mathematica 并不是万能的。 Mathematica 之所以能求出 π/17 的三角函数值,可能仅仅是因为它预先存储了这个值。
我又开始在想, Mathematica 化简不出,别的符号计算软件能把它化简出来吗?是否存在这么一个牛 B 的数学软件,输进去的任意表达式都可以化简成你想要的形式?后来我想到,这和软件牛不牛 B 是没有关系的。任意符号表达式的化简求值从理论上说就是一个不可能完成的任务。
首先,我们将说明化简求值至少是 NP-hard 的。我们下面将说明,我们能够把任意一个整数线性规划问题“编码”为级数的化简求值问题。例如,考虑下面这个整数规划问题:
最大化 x+y 的值,其中 x 、 y 满足:
x > 0
y > 0
x ≤ 5
y ≤ 5
2x + y < 12.5 x="" +="" 3y=""><>
我们将考虑它的两个判定问题: x+y 是否能取到 8 ? x+y 是否能取到 9 ?
为了把这个问题用一个级数表达出来,我们只需要用到这么一个函数: f(x)=x/√x^2 。这个初等函数有一个非常有用的性质:当 x 大于 0 时, f(x) = 1 ;当 x 小于 0 时, f(x) = -1 。因此, (f(a – b) + 1)/2 就可以用来判断 a 是否大于 b (假设 a 、 b 不相等)。如果 a 大于 b ,函数值为 1 ;否则,函数值为 0 。
为了判断出 x+y 是否能取到 8 ,我们只需要计算下面这个级数的值即可(我们用“大于 7.5 ”来代替“大于等于 8 ”,以排除分母为 0 的情况)。如果整个级数的值为 0 ,表示级数的每一项中的各个因式里至少有一个为 0 ,换句话说不管 x 和 y 取多少,这些限制条件中总有一个不成立。反之,如果整个级数的值为一个正整数,那么这个正整数就表示符合要求的解有多少个。 Mathematica 告诉我们, x+y≥8 有一组解,但 x+y≥9 是没有解的。
然而,整数规划问题是 NP-hard 的,因此级数的化简求值不会有什么有效的算法。
事实上,实际情况可能更糟:一般的级数很可能根本没办法化简求值。考虑定义在整数范围内的函数 g(x) = (f(x + 0.5) + f(x – 0.5))/2 。容易看出,当 x 为正整数时, g(x) = 1 ;当 x 为负整数时, g(x) = -1 ;当 x 为 0 时, x+0.5 和 x-0.5 一正一负,因此 g(x) = 0 。利用函数 g(x) ,我们就能构造出函数 isNonZero(x) = (g(x))^2 ,该函数的取值范围只有 0 和 1 ,并且函数值为 1 当且仅当 x 为非零数。另外,我们可以顺便定义出 isZero(x) = 1 – isNonZero(x) 。
考虑这么一个无穷级数:
Σ(a=1..∞) Σ(b=1..∞) Σ(c=1..∞) isZero(a^3 + b^3 – c^3)
如果化简求值的结果为 0 ,则表明对于所有的正整数 a 、 b 、 c ,a^3 + b^3 – c^3 都不为0。再把级数增强为
Σ(n=3..∞) Σ(a=1..∞) Σ(b=1..∞) Σ(c=1..∞) isZero(a^n + b^n – c^n)
如果哪个软件能瞬间求出它化简求值的结果,不就相当于证明了 Fermat 大定理吗?
鉴于 Fermat 大定理已经被证明过了,于是我开始着手构造一些更震撼的东西。考虑级数
Σ(a=2..n) Σ(b=2..n) isZero(a*b – n)
若级数值为 0 ,表明 n 不可能等于两个大于 1 的整数的乘积,也就是说这个数是一个质数。因此,可以定义
isPrime(n) = isZero( Σ(a=2..n) Σ(b=2..n) isZero(a*b – n)) )。
下面这个级数化简求值的结果为 1 当且仅当 n 能表示为两个质数之和:
canBeExpressedAsSumOfTwoPrimes(n) = isNonZero( Σ(i=2..n-2) (isPrime(i) * isPrime(n-i)) )
再考虑下面这个级数
Σ(n=2..∞) isZero(canBeExpressedAsSumOfTwoPrimes(2n))
如果级数不为 0 ,就表明存在某个 n 使得 canBeExpressedAsSumOfTwoPrimes(2n) 不成立。因此,如果有什么万能表达式化简软件具有化简这个级数的能力,我们就能够证明或推翻 Goldbach 猜想了。看来,计算机的符号运算也是有极限的。
当然,以上都是我个人的一些见解,我也不知道类似的话题是否有探究过,与此相关的还有些什么样的结论。如果大家发现了什么错误,或者想到了什么更牛的,欢迎加入讨论。
Update: 似乎有这样的结论:由于 Diophantine 方程是否有解是不可判定的,而它能规约到级数化简求值,因此后者也是不可判定的。
联系客服