[FOM] Undecidable statements (physics)

Sam Sanders sasander at me.com
Tue Feb 5 17:50:58 EST 2019

Dear FOM,

Arnon’s below paper/message reminds me of the following paper:


When I talked to the first author (and yes, that’s his real name), he told me that

(i) yes, the halting problem can be derived from a solution to the following problem in Quantum Mechanics:

 Given the Hamiltonian of a quantum many-body system, is it gapped or gapless?

(ii) no, the kind of system and Hamiltonian (in their proof) that give rise to the Halting problem are NOT 
natural from the pov of physics (by any stretch of the imagination).  

I suspect the same will always turn out to be true for these independence claims:  sure, the general
case gives you the Turing jump, CH, or large cardinals, but when you look at what people in the 
trenches actually use/do, they make no use of the ‘artificial' case you used in your independence proof.   

And when noise enters the equation… many a diagonalisation breaks down.  

These papers are of course excellent work, but one should not exaggerate the foundational import.  



PS: CH is referred to as a ‘paradox' in the Nature blurb Arnon points out below.  This could be
construed as inaccurate...

> On 4 Feb 2019, at 22:36, Arnon Avron <aa at tau.ac.il> wrote:
> The following article should be of interest to people 
> on this list -  especially for those who find it important
> to connect logical undecidability results to problems
> that "real" researchers in math or cs are interested in.
> (To what extent this is indeed the case here I cannot tell.)
> https://www.nature.com/articles/d41586-019-00083-3
> This is the paper to which the article refers:
> https://www.cs.tau.ac.il/~shpilka/publications/BDHMSY18.pdf
> Arnon Avron
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> https://cs.nyu.edu/mailman/listinfo/fom

More information about the FOM mailing list