Why some physicists are excited about the undecidability of the spectral gap problem and why should we

Vladik Kreinovich, The Logic in Computer Science Column by Yuri Gurevich


Since Turing’s time, many problems have been proven undecidable. It
is interesting though that, arguably, none of the working physicist problems
had been ever proven undecidable – until T. Cubitt, D. Perez-Garcia and
M. M. Wolf proved recently that, for a physically reasonable class of systems,
no algorithm can decide whether a given system has a spectral gap.
We explain the spectral gap problem, its importance for physics and possible
consequences of this exciting new result.

Full Text:



  • There are currently no refbacks.