2022-04-01 (Undecidable problems

Yuji Tachikawa 的愚人节文章。如他所写

In the hope of providing some intellectual entertainment on April fool's day of this dark year,....

确实收获到了一些乐趣，想起了以前和几个朋友“胡说八道”的日子。

另外致谢部分和妻子的互动部分也很有意思。

Undecidable problems

我们早已熟悉了两种物理里面的不可预测性：

1. 量子力学告诉我们只能预测事件发生的概率；
2. 混沌系统会指数级放大微小扰动令我们很快丧失对系统的预测能力，即便不考虑量子效应。

文章要讲的是另外一种不可预测：我们无法判断一个系统是否具有某种性质！
这里无法判断是指，没有一个具体的算法（algorithm）来判断。所以这个无法判断并不是因为技术上的原因，而是原则上无法判断。
要判断某种性质，就要对系统进行求解，当然可能这个求解十分困难。比如对于可积系统，寻找lax pair 很困难，一般来说也没有一个算法。但是其实，可以利用算法找到系统所有的对称性，从而得到所有的守恒量，有了所有的守恒量后就可以构造lax pair。所以是否存在lax pair并不是无法判断的。

其实这种不可预测的情况在计算理论(theory of computation)还有数学中很常见。文章里主要用的一个情况就是：图灵机的停机问题(Halting problem)。
图灵机具有有限长度的程序和有限的内部状态，但是他的存储是无穷的。根据程序，图灵机按部就班的更新自己的内部状态还有改写有限的存储内容。
我们可以认为图灵机的输入是自然数，然后根据程序输出一个结果然后停止。但是有可能程序陷入一个死循环导致图灵机永远不会停止。
一个结论是不存在一个图灵机他的程序可以判断图灵机是否会停止。

证明这个我们需要引入一个通用的图灵机：考虑任何一个图灵机，把所有可能的输出 排序，这样每一个也是一个数, 这些数构集合。有两个输入 ，他的程序是判断 是否在里，如果在的话输出。
如果存在一个通用的图灵机，那么我们可以问他是否能判断自己是否会停机，这样我们可以设置一个矛盾，就是当他停机的时候输出的结果是自己不停机。

数学中一个著名的无法判断的例子就是Godel的不完备定理：一个自洽完备的理论，不能证明也不能证伪自己的完备性。

另外一个例子是Hilbert‘s 10th problem：是否存在一个有效的方法判断Diophantine 方程是否有解。
Diophantine 方程是一个具有整数系数的多项式方程：

这个问题已经被解决，答案是不存在。因为这个问题可以转化成一个停机问题。

Undecidable problems in physics

所以想法就很简单：如果我们能把一个问题转为成一个停机问题，就得到了一个不可判断的物理问题。

自旋系统

比如我们可构造一个2维的自旋格点系统的基态能量满足

1. 如果 不停机
2. 如果 停机

当然构造这样的系统需要一点想象力。自旋的状态对应了图灵机的内补状态，Hamiltonian量则与图灵机的程序有关。

超对称破缺

我们考虑一个Wess-Zumino model 具有 个chiral superfields ,并且他的superpotential 的形式是

这里 是Diophantine 函数。这样这个model是否具有non-trivial 真空（超对称是否破缺）的问题即是否具有non-trivial的极值点，就转成了是否有解的问题。我们刚刚提到这个问题是无法判断的。

https://plato.stanford.edu/entries/computability/#Bib 一个关于计算科学的科普。