3 ms·

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 peri

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).

martincmartin 11y ago
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.
lorenzhs 11y ago
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. [1] https://en.wikipedia.org/wiki/Undecidable_problem https://en.wikipedia.org/wiki/Undecidable_problem
sp332 11y ago
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_of_.CE.A3 https://en.wikipedia.org/wiki/Busy_beaver#Non-computability_...