Become a fan of Slashdot on Facebook


Forgot your password?
DEAL: For $25 - Add A Second Phone Number To Your Smartphone for life! Use promo code SLASHDOT25. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. Check out the new SourceForge HTML5 Internet speed test! ×

Comment Re:Booor-ing... (Score 5, Informative) 180


Quantum computers can change the rate at which problems are solved, but not whether or not a solution is technically achievable through computation.

Goldbachs' conjecture and the Riemann hypothesis might be provable through an accelerated brute forcing of all possible proofs if, for example, P=NP and algorithmic degrees and coefficients are reasonable, but this is only because such a brute force may be doable already with a sufficiently ginormous length of time (assuming that they are in fact provable to begin with, which some true propositions are not (unless our math is internally inconsistent)).

The halting problem cannot be solved for arbitrary Turing machines. Period. No algorithm, as we think of them, using quantum computers or not, will get around the fact that such a solution would create a logical inconsistency (a program could determine whether or not it itself would halt, and then do the opposite, but then it would have been wrong, which it can't be by assumption, and so reality bursts into flames). The only possible catch is that a technique that cannot be encoded in a Turing machine would not cause this particular logical inconsistency to arise. Basically this leaves an opportunity for solution through revelation. Or not, depending on your philosophical persuasion towards flaimbait and the rest of existence.

Again, though, quantum computers do not allow one to execute algorithms that are beyond simulation (albeit more slowly) on classical computers. What ifs are fun, but this one, at least in part, is worse than baseless.

Slashdot Top Deals

Artificial intelligence has the same relation to intelligence as artificial flowers have to flowers. -- David Parnas