誰能用大白話解釋一下 譜隙問題 怎麼就哥德爾不完備了？

http://arxiv.org/abs/1502.04573

Paradox at the heart of mathematics makes physics problem unanswerable : Nature News Comment

《自然》 要覽：關於「譜隙問題」的問題

---

哥德爾不完備在這裡所指的，似乎是在基本二維晶格假設下、使用量子力學方法進行底層能隙計算無法完成，根據這篇nature的描述，有限晶格理想狀況下可以得到具體結果，然而由於實際晶體的各種無規原子數漲落，能隙的變化/開合迅速，於是能隙無法進行預測，這是與無限二維晶格計算多項式時間內無結果產生相類似的。

一點淺見，沒有細看他們的研究，這個問題需要對數論以及楊米爾斯mass-gap有一定的理解，等方家作答。

---

謝邀。這裡的哥德爾不完備指是否存在譜隙是不可判定的（不可判定指的對一個答案是yes或no的問題，不存在一個總能給出正確答案的演算法）。但是這個文章並不意味著對於一個實際特定的物理問題，答案是不可判定的。這個文章研究的是極限情況下的演算法複雜性，而不是一個實際特定的物理問題。

---

原文：

We show that the spectral gap problem is undecidable. Specifically, we construct families of translationally-invariant, nearest-neighbour Hamiltonians on a 2D square lattice of d-level quantum systems (d constant), for which determining whether the system is gapped or gapless is an undecidable problem

他們構造了一個足夠複雜的情況使得判定物理模型中出現的gap是否存在的問題是不可判定的。這個不可判定是指停機問題那種意義上的不可判定。

為什麼會提到哥德爾不完備性？這和形式系統的不完備性有什麼關係嗎？

因為這種不可判定性本來就能看作是哥德爾不完備性定理的推論

Stephen Cole Kleene (1943) presented a proof of G?dels incompleteness theorem using basic results of computability theory. One such result shows that thehalting problem is undecidable: there is no computer program that can correctly determine, given any program P as input, whether P eventually halts when run with a particular given input. Kleene showed that the existence of a complete effective theory of arithmetic with certain consistency properties would force the halting problem to be decidable, a contradiction. This method of proof has also been presented by Shoenfield (1967, p. 132); Charlesworth (1980); and Hopcroft and Ullman (1979).

from wikipedia，G?dels incompleteness theorems詞條

類似這樣的問題，在特定的物理模型里發現難以求解的情況

有一個專門的領域來研究，稱為哈密頓複雜度，見綜述arXiv:1401.3916v3 [quant-ph]

在這裡可以發現存在一系列關於譜隙的大小的問題是屬於QMA-hard的，這類問題是雖然可以判定，但是需要指數級時間複雜度（即使用了量子計算機也不能克服），實踐上也是可能陷入幾乎無法求解的情況

另外，這個問題和量子沒有必然關係

純經典力學的模型也可以構造出不可判定的物理問題，見(Phys. Rev. Lett. 64, 2354 (1990))

大致思路是，將一個已經確定是不可判定的問題（例如停機問題）或者是複雜度很大的問題「編碼」到這個系統里去，使得判斷系統的能隙是否存在等價於判定原本的問題

=================以下是個人觀點======================

這個結果並不比「人類可以造出電腦」更值得驚奇……

有一個你非常熟悉的物理系統，就正受著這篇論文所描述的這類由「哥德爾不完備性」所生的限制，即：你的電腦==

有關論文摘要中所寫的

Our results imply that for any consistent, recursive axiomatisation of mathematics, there exist specific Hamiltonians for which the presence or absence of a spectral gap is independent of the axioms.

These results have a number of important implications for condensed matter and many-body quantum theory.

第一段話雖然聽起來很神奇很誇張，但是這確實是對的，因為如果有這樣的一致而又能遞歸公理化的形式系統T存在，那麼就可以利用一台能夠枚舉T中的形式證明的圖靈機來判定上述的問題，這和它的不可判定性矛盾。

值得懷疑的反而是第二段

因為它沒有成功說明這種故意弄得很奇怪的」specific Hamiltonian「真的在自然界普遍存在

如果在自然界根本不存在這樣的情況，其實這結果對凝聚態物理和量子多體理論都不是很有意義……

---

因為它在現實世界中不存在。依據現有模型沒法算出來gap消失的情況。原文說計算需要無限久

而且也不能通過計算非常小的gap去推斷gap消失的狀況。那個點根本就是不連續的。原文change abruptly

貌似有點像weierstrass function？

不一定對。我學生物的，不懂理論物理

---

推薦閱讀：