图灵机的能力

目前最流行的符号推导软件具有一些基本的公式推导和逻辑推导的能力，但是这些软件还远远谈不上智能。例如以前我使用Mathematica和Maple的时候，许多结果需要用无穷级数来表达的积分之类的东西是无法自动被这些软件推导出来的。

但事实上我们人类所能够写出的无穷项级数才能精确表示的数学表达式，必然可以用有限个符号所刻画。有时候我们使用“...”来表示无穷级数的项，事实上这是因为我们能够在前面几项中看出规律的时候才使用这种缩写，而这种规律自然是有限符号可以刻画的。或者我们看不出其中的规律，只是求出了前面几项，那么我们所得到的结果自然也就不是完整的，仅仅是只需前面几个有限项就能够描述的非精确描述，这种情况下我们所得到的不完整的计算结果仍然是有限符号可以表达的。

这样，只要引入适当的推导规则，那么许多无穷级数解也可能可以被符号推导软件所推导出来。当然，对于现有的符号计算软件，引入适当的推导规则这种事情还要人来做，软件在闲着没事的时候自己不会去尝试发现这些原来所不具备的推导规则。

不过即便软件在闲着的时候会主动做一些发现新规则的探索游戏，仍然受到一个限制：由于计算机本身的可靠性，这些软件基本上是不会出随机错的，其能力会直接受歌德尔不完备性定理的限制。但图灵早在歌德尔不完备性定理刚刚提出不久就曾经澄清过，歌德尔不完备性定理所限制的是那种仅仅能输出正确结果的机器，而不能限制可能输出错误结果的机器（Penrose在这个问题上确凿无疑滴错乐）。因此，一台挂接了真随机数发生器的以一定概率出错的图灵机（例如读写会以一定的概率把1当成0或者把0当成1，状态迁移会以一定的概率迁入错误的状态，状态迁移表会以一定的概率发生不确定的改变），就不再受歌德尔定理的限制。而且不但如此，不挂接真随机数发生器，使用图灵机自己生成伪随机数，也可以在随机预言模型下（Random Oracle）以任意高的精度模拟带有真随机数发生器的图灵机，只有对那些在计算过程中刚好会出现某种匹配了伪随机数发生器算法序列的问题上显示出其局限。

曾经有人以为量子计算机的能力超越图灵机，但有人做过研究之后认为量子计算机的能力并不能超越带有真随机数发生器的图灵机。目前已经严格证明所有完全由qubit构成的系统最多等价于图灵机，但对于一般的量子计算系统是否都等价于图灵机尚未给出最后的答案。

超限计算在计算能力上超越图灵机，但是需要能够识别无限数量的符号或者拥有无限个状态，这里的无限甚至可以不是可数的无限。我们可以讨论超限计算的能力极限，因为这只需要有限个符号。但是我们却没有能力直接利用这种模型进行实际的计算。虽然物理量的值往往被当作实数，但由于误差的存在，导致事实上我们能够区分的取值只是有限个。虽然量子态在量子力学中是无限精度的，但测量所得的结果只能是本征值，本征值要么只是离散，要么是连续但有误差的，量子态的精确信息在测量过程中丢失了。因此我们现在不知道任何一种在物理上实现可以被我们利用的超限计算机的方式。

我猜，有限状态识别有限符号的计算机的能力上限就是图灵机，不可能超越图灵机，不知道是否能够对此做出严格的证明。