Re:A first for physics: Fundamental quantum physics problem ...
by adrianN on Thursday December 10, 2015 @03:09AM
(#10709496)
Tilings are a neat way to simulate Turing machines, so it's not super surprising that they show up in an undecidability proof:
Re:A first for physics: Fundamental quantum physics problem ...
by fallingfrog on Thursday December 10, 2015 @09:03AM
(#10710605)
So if I'm understanding this right, they proved that you can't calculate the bandgap of some class of systems of arbitrary size in any predetermined finite period of time, right? I guess when you really think about it, the opposite finding would be much more surprising. (That you could calculate the bandgap of any system of any size in some finite time period, however large).
Re:A first for physics: Fundamental quantum physics problem ...
by sp332 on Thursday December 10, 2015 @11:35AM
(#10711502)
It's not a constant period of time. The amount of time is allowed to increase with the size of the system. In fact it's allowed to increase quadratically, or exponentially, or factorially, or whatever - it will never be enough. Whatever algorithm you come up with for calculating the rate of expansion, you will always underestimate the amount of time (for a sufficiently large system).
https://en.wikipedia.org/wiki/Busy_beaver#Non-computability_...
Re:A first for physics: Fundamental quantum physics problem ...
by lorenzhs on Thursday December 10, 2015 @11:32AM
(#10711485)
No, it's worse than that: From Wikipedia [1]: "In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer."
The definition of algorithm includes termination after a finite amount of steps. This number isn't predefined.
Re:A first for physics: Fundamental quantum physics problem ...
by martincmartin on Thursday December 10, 2015 @09:23AM
(#10710701)
The finite period of time isn't predetermined, and different systems could take different amounts of time. So, its not intuitive in the way you imply.
Re:A first for physics: Fundamental quantum physics problem ...
by Natanael_L on Thursday December 10, 2015 @07:47AM
(#10710346)
Next up: tie this info cryptography and information theoretic complexity, so we can attempt to create meaningful algorithm security proofs.
Just when I thought linking quantum mechanics with Turing completeness was cool, they went one step further and linked them using aperiodic tilings.