《计算理论导引（原书第3版）》计算理论导引揭示计算的本质

我们计算 3×7=21，与计算 21=3×7 有什么不同？3×7 蕴含着 21，21 也蕴含着 3×7，区别在于求解过程和答案形式。

一般来说，问题不仅和其他已知的公理、原理一起构成了蕴含着答案的文本，更重要的是，它本身限定了答案的形式。计算过程就是以逻辑方法变换文本形式，最终构造出答案的过程。这个说法适用于可判定性和可识别性，两者区别在于后者多出了一个文本，即待验证的答案。

由此，可得出第一个结论：可计算性就是逻辑性。反过来说，一个问题不可计算，意味着它的已知条件不充分，以致不能逻辑地变成答案形式。

接下来，让我们从抽象的逻辑空间回到现实四维时空中。任何信息的传递都是时空变换的结果，任何信息也都保存在四维时空中。问题和答案一定具有某种物理形态，计算的逻辑过程也肯定表现为某种物理过程。换言之，计算必须耗费能量。

由此，我得出第二个结论：计算复杂度问题就是物理耗能问题。不论是时间复杂度还是空间复杂度，归根结底都是在测量计算所耗费的能量。

以上是对可计算性和计算复杂度的认识。

最后的问题是，当人类耗费能量找到了一个又一个问题的答案，我们最终能得到什么？仅仅是热力学所预言的“热寂”还是在宇宙以外的某处积累着知识的势能，正如阿西莫夫在《最后的问题》中所说的：“AC 的意识包含了曾经的宇宙中的一切，在如今的混乱之中沉思、孵育。一步一步地，事情将会被做成。然后 AC 说道：要有光！于是就有了光。”

2023 年 5 月 19 日写于上海。