*Nature*, has been receiving some attention (at least as judged by the number of my facebook friends who have shared or commented on it!) It’s been called “genuinely shocking, and probably a big surprise for almost everybody working on condensed-matter theory” (Christian Gogolin, quoted by Castelvecchi).

I don’t mean to rain on anyone’s parade, but I wonder
whether it

*should*be regarded as surprising. It seems to me that the result follows from something that is well-known in the field of computable analysis: undecidability of equality of real numbers.
Turing machines operate on integer inputs; to deal with real
numbers, we use rational approximations.
Since there are countably many rationals, we can index them by
natural numbers; pick your favourite enumeration, and let

*q*be the rational number indexed by_{k}*k*. A real number*x*is computable if and only if there is an algorithm that delivers rational approximations to*x*, as a function of desired degree of accuracy; that is, if there is an algorithm that delivers*k*(*m*) as a function of*m*, such that the distance between*x*and*q*_{k}_{(m) }is always less than 2^{–m}. A sequence of numbers {*x*} is a_{n}*computable sequence*if and only if there is an algorithm that delivers a rational number that is within a distance 2^{–m}of*x*, as a function of_{n}*n*and*m*.
Now, if I hand you an algorithm for computing a number

*x*(or an oracle that delivers rational approximations to any desired degree of precision), can you decide whether or not the number is equal to 0?
If the number is

*not*equal to 0, then knowing a sufficiently precise rational approximation to the number will tell you that. But if you keep computing closer and closer rational approximations and don’t find the number bounded away from zero, then you don’t know whether the number is zero, or whether a closer rational approximation will bound it away from zero. You don’t know when to stop.
This should sound familiar, as it is reminiscent of the
Halting Problem. And, in fact, it is
easy to show that the undecidability of equality is equivalent to the Halting
Problem.

Given a Universal Turing machine

*T*, it is easy to construct a computable sequence {*x*} such that_{n}*x*is greater than zero if_{n}*T*halts on input*n*and is equal to zero if it doesn’t (see my 1995 and 1997). So, if we could effectively decide which members of the computable sequence {*x*} are equal to zero, we could solve the halting problem._{n}
This means that, if we have

*any*decision problem that asks whether a given quantity that is a calculable function of real-valued input parameters is equal to zero or not, it’s an undecidable problem. All computable functions on the reals are continuous! (Weihrauch 2000, Th. 4.3.1)
This is why I’m not surprised by the Cubitt

*et al.*result.
The result concerns 2-dimensional

*L*×*L*lattices of spins, with nearest-neighbour interactions. The system is*gapped*if there is a number*γ*such that, for sufficiently large*L*, the difference between the energy of the ground state and the energies of all excited states is at least*γ*. The system is*gapless*if, in the thermodynamic limit, it has continuous spectrum above the ground state. The authors construct a family of interaction Hamiltonians*h*(*φ*), depending on an input parameter*φ*, such that whether or not the spectrum is gapped depends on the value of*φ*, and they rig things so that there is a computable sequence of numbers {*φ*(*n*)} such that whether or not the system with interaction Hamiltonian*h*(*φ*(*n*)) is gapped or gapless depends on whether or not a Universal Turing machine halts on input*n*.
If all that is needed to show that the problem is
undecidable is to construct a family of Hamiltonians, depending on input
parameter

*φ*, such that there is a computable sequence {*φ*} of input parameters such that the system is gapped if a Universal Turing Machine halts on input_{n}*n*and gapless if it doesn’t, then I can’t help but wonder whether it could be done more simply.
Suppose we construct interactions

*h*(*λ*) such that whether the system is gapped or gapless depends on whether the input parameter*λ*is greater than zero. Then, without further ado, there is, as mentioned above, a computable sequence {*λ*} of input parameters such that the system is gapped if a Universal Turing Machine halts on input_{n}*n*and gapless if it doesn’t, and we can conclude that the problem is not effectively decidable as a function of the input parameter.**References**

Castevecchi,
Davide (2015), “Paradox at the heart of mathematics makes physics problem
unanswerable.”

*Nature News*, 9 December 2015, http://www.nature.com/news/paradox-at-the-heart-of-mathematics-makes-physics-problem-unanswerable-1.18983.
Cubitt, Toby S., David Perez-Garcia, & Michael M.
Wolf, “Undecidability of the spectral gap”

*Nature***528**(10 December 2015), 207–211.
Myrvold,
Wayne C. (1995). “Computability in Quantum Mechanics,” in Werner
DePauli-Schimanovich, Eckehart Köhler, and Friedrich Stadler, eds.,

*The Foundational Debate: Complexity and Constructivity in Mathematics and Physics*(Kluwer Academic Publishers, 1995), pp. 33–46. Available at http://philpapers.org/rec/MYRCIQ
——— (1997). “The
Decision Problem for Entanglement.” In
Robert S. Cohen, Michael Horne & John Stachel (eds.),

*Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies for Abner Shimony*. (Kluwer Academic Publishers), pp. 177–190. Available at http://philpapers.org/rec/MYRTDP
Weihrauch,
Klaus (2000).

*Computable Analysis: An Introduction.*Springer.
## No comments:

## Post a Comment