SoylentNews is people
SoylentNews
As Science alert reports, researches have proven for the first time, that a fundamental problem of quantum mechanics, the problem whether a material has an energy gap, is equivalent to the halting problem, which states there is no way to always determine in finite time whether a given program will ever terminate. It it the first and most well known example of an undecidable problem.
In the words of the scientists, as quoted by the article:
"What we've shown is that the spectral gap is one of these undecidable problems. This means a general method to determine whether matter described by quantum mechanics has a spectral gap, or not, cannot exist. Which limits the extent to which we can predict the behaviour of quantum materials, and potentially even fundamental particle physics." said one of the researchers, Toby Cubitt from University College London in the UK.
So why is this important? To quote the article:
Why are spectral gaps so important? They're a central property of semiconductors, which are crucial components of most electrical circuits, and physicists had hoped that if they'd be able to work out whether a material is superconductive at room temperature (a highly desirable trait) simply by extrapolating from a complete-enough microscopic description.
[More After the Break]
But it goes even deeper:
There are some big implications of this discovery, especially given that there's a US$1 million prize at stake from the Clay Mathematics Institute for anyone who can prove whether the standard model of particle physics – which explains the behaviour of the most basic particles of matter in the Universe – has a spectral gap, using standard model equations.
"It's possible for particular cases of a problem to be solvable even when the general problem is undecidable, so someone may yet win the coveted $1 million prize," said Cubitt. "But our results do raise the prospect that some of these big open problems in theoretical physics could be provably unsolvable."
However, the discovery may also open up new possibilities:
"The reason this problem is impossible to solve in general is because models at this level exhibit extremely bizarre behaviour that essentially defeats any attempt to analyse them," said co-author David Pérez-García from the Universidad Complutense de Madrid in Spain.
"But this bizarre behaviour also predicts some new and very weird physics that hasn't been seen before. For example, our results show that adding even a single particle to a lump of matter, however large, could in principle dramatically change its properties. New physics like this is often later exploited in technology."
The team is now testing whether their mathematical models will hold up when tested in the lab with real quantum materials. Let's hope that problem is a little more solvable.
The actual scientific article is in Nature, an open access version can be found on arXiv.
(Score: 1) by YeaWhatevs on Wednesday December 16 2015, @11:02PM
Right. For instance, the article summary says the physics problem is equivalent to the halting problem. I expect they butchered the science in making this equivalence, but it means the halting problem can't be solved with a Turing machine, and so neither can the physics problem. This means, we can't solve the general problem using any modern computer, no matter how powerful. There are of course, at least in theory, machines that are non-turing (no, not quantum computers), so for all practical purposes we will probably not solve the problem any time soon, but it doesn't mean we have exhausted all possibilities.
(Score: 0) by Anonymous Coward on Thursday December 17 2015, @08:25AM
I don't think you understand.
In brief, here's their problem:
There's a system characterised, among other things, by the number of molecules N it has and the total energy E.
Find a formula that will tell you what energies the electrons in this system can have for all N and E.
Their result is that in order to solve this problem, you actually need to do it for each value of N separately, and the fastest way to solve it is to actually build the system, and check what you get.
Obviously, in this scenario the analogue representation of the system (or the system itself) is what you call a "non Turing machine".
But the important message is that it is impossible to build a consistent "statistical physics" for a certain class of systems; the limit of large N for these solutions does not actually exist.
Obviously, in practical terms it may turn out that a formula that works 99.99% of the time may be found (hell, for macroscopic systems the number of molecules is not actually constant and there are impurities as well), but that is not their concern.