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, Funny) by Anonymous Coward on Wednesday December 16 2015, @08:30PM
Since practical computers have a limited amount of memory, no halting problem!
*ducks*
(Score: 0) by Anonymous Coward on Wednesday December 16 2015, @10:00PM
Um, a computer program can run definitely without consuming more memory.
(Score: 2) by mhajicek on Thursday December 17 2015, @05:40AM
Basic:
10 IF RND 0.999999 GOTO 10
Doesn't take much memory. How long will it run?
The spacelike surfaces of time foliations can have a cusp at the surface of discontinuity. - P. Hajicek
(Score: 2) by mhajicek on Thursday December 17 2015, @05:42AM
there was supposed to be a less-than before the number. I failed to preview.
The spacelike surfaces of time foliations can have a cusp at the surface of discontinuity. - P. Hajicek
(Score: 0) by Anonymous Coward on Thursday December 17 2015, @07:00AM
It is implementation dependent, but should be expected to run for about half a million cycles.
Based on syntax, I Ruled out C64 basic [c64-wiki.com]
The syntax for Compaq BASIC [hp.com] matches. Note that without the RANDOMIZE key-word (which probably uses the system clock), the output of the program is deterministic.
(Score: 0) by Anonymous Coward on Thursday December 17 2015, @04:17PM
Correction: that program should run 1 or 2 cycles, depending on implementation.
Assuming Compaq Basic, the first number will be .76308, which is less than 0.99999.
(Score: 2) by mhajicek on Thursday December 17 2015, @08:03PM
I agree that it should run about half a million cycles. But if you have a true random number generator you don't know for sure. It's a vanishingly small chance, but execution could outlast the universe.
The spacelike surfaces of time foliations can have a cusp at the surface of discontinuity. - P. Hajicek
(Score: 0) by Anonymous Coward on Thursday December 17 2015, @10:17PM
A true random number generator would be getting input from the outside world. Of course you would not be able to prove whether or not it halts by examining only the system itself.