3 ms·

I've often thought that results in computer science about the performance characteristic of classes of algorithms are also, in a sense, making statements about

I've often thought that results in computer science about the performance characteristic of classes of algorithms are also, in a sense, making statements about physics. In other words, in a universe where bits of information can be sent instantaneously through worm holes, it may not be correct to say that there's no better comparison-based sort bound than O(n log n). I'm not an expert at physics or computational complexity so maybe my intuition is way off here. But I wonder if, when I hear about innovations in "hypercomputation", I should understand the researchers to be making claims which are essentially as likely to pan out as a claim of having sent bits through wormholes.

mikeash 9y ago
Results about computational complexity are always relative to some specific model of computation. For example, a standard Turing machine cannot sort in O(n log n) time. Because it has to walk along the tape one position at a time, it takes longer. When the big-O of an algorithm is given without mention of the machine model, it typically refers to a machine with random-access memory, since that's approximately what real computers have. So yes, physical possibility is definitely a big factor here, even if it's not always stated explicitly. If it were impossible to build practical random-access memory, then that wouldn't be the standard model used for computational complexity. Consider the big question of whether P=NP. The question itself is unrelated to physics, since P is defined as polynomial-time algorithms on deterministic Turing machines, and NP as polynomial-time on nondeterministic Turing machines. But the question gets a lot of attention in part because it's considered to be impossible to actually build a nondeterministic Turing machine. If that were untrue, then we could solve problems in NP in polynomial time even if P≠NP. In theory, you could build something like a nondeterministic Turing machine (without infinite memory, but close enough, much like we consider real-world computers to be close enough to normal Turing machines) if you could, say, send information back in time, or if you could split the universe into arbitrary many parallel universes, then destroy all but one. Obviously, nobody has the slightest idea of how to do this, but at least there are some vague, crazy possibilities. Hypercomputation is even worse. To accomplish it in anything like physics as we know it would require infinite time, space, and energy. In theory you can get infinite time by putting your computer into just the right orbit around a rotating black hole. Infinite space and energy are somewhat harder to come by. (You know you're in trouble when you need to do something harder than putting something into a precise orbit around a rotating black hole.) There's always the possibility of new physics. Nothing says it's impossible for there to exist some fundamental particle which acts like a Turing oracle when you poke it just right. But the chances seem pretty poor. In short, yes, barring any massive physics breakthrough, treat hypercomputation as a theoretical math construct, nothing more.
- davesque 9y ago
  Thanks for taking my musings seriously and for giving such a thoughtful reply.
- davrosthedalek 9y ago
  You don't have to put the computer in the right orbit, you have to put yourself into the right orbit. Your time goes slower, so it gives the computer outside more time to work. Please don't try it at home.

mikeash 9y ago

Results about computational complexity are always relative to some specific model of computation. For example, a standard Turing machine cannot sort in O(n log n) time. Because it has to walk along the tape one position at a time, it takes longer. When the big-O of an algorithm is given without mention of the machine model, it typically refers to a machine with random-access memory, since that's approximately what real computers have. So yes, physical possibility is definitely a big factor here, even if it's not always stated explicitly. If it were impossible to build practical random-access memory, then that wouldn't be the standard model used for computational complexity. Consider the big question of whether P=NP. The question itself is unrelated to physics, since P is defined as polynomial-time algorithms on deterministic Turing machines, and NP as polynomial-time on nondeterministic Turing machines. But the question gets a lot of attention in part because it's considered to be impossible to actually build a nondeterministic Turing machine. If that were untrue, then we could solve problems in NP in polynomial time even if P≠NP. In theory, you could build something like a nondeterministic Turing machine (without infinite memory, but close enough, much like we consider real-world computers to be close enough to normal Turing machines) if you could, say, send information back in time, or if you could split the universe into arbitrary many parallel universes, then destroy all but one. Obviously, nobody has the slightest idea of how to do this, but at least there are some vague, crazy possibilities. Hypercomputation is even worse. To accomplish it in anything like physics as we know it would require infinite time, space, and energy. In theory you can get infinite time by putting your computer into just the right orbit around a rotating black hole. Infinite space and energy are somewhat harder to come by. (You know you're in trouble when you need to do something harder than putting something into a precise orbit around a rotating black hole.) There's always the possibility of new physics. Nothing says it's impossible for there to exist some fundamental particle which acts like a Turing oracle when you poke it just right. But the chances seem pretty poor. In short, yes, barring any massive physics breakthrough, treat hypercomputation as a theoretical math construct, nothing more.

davesque 9y ago
Thanks for taking my musings seriously and for giving such a thoughtful reply.
davrosthedalek 9y ago
You don't have to put the computer in the right orbit, you have to put yourself into the right orbit. Your time goes slower, so it gives the computer outside more time to work. Please don't try it at home.