Douglas_Knight comments on Can somebody explain this to me?: The computability of the laws of physics and hypercomputation - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (53)
There are spacetime models in general relativity (i.e. solutions to the Einstein equations) that permit hypercomputation. In a Malament-Hogarth spacetime, there are wordlines such that an object traveling along the worldline will experience infinite time, but for an observer at some point p outside the wordline, the time it takes for the object to traverse the worldline is finite, and the wordline is entirely within p's causal past. So if you had a Turing machine traveling along this wordline, it could send a signal to p if and onliy if it halted, and the observer at p is guaranteed to receive the signal if the machine ever halts. No infinite-precision measurements are involved (unless perhaps you believe that a Turing machine operating reliably for an indefinite period of time is tantamount to an infinite-precision measurement).
Are these spacetimes physically possible? Well, like I said, they satisfy the basic laws of GR. However, they are not globally hyperbolic, which means there is is no space-like surface (analogous to an "instant of time") such that providing all data on that surface fully determines the data over the rest of space-time uniquely. In other words, determinism of a particularly strong variety fails.
The strong version of the cosmic censorship hypothesis essentially states that a physically reasonable spacetime must be globally hyperbolic, so if you take it as a criterion of physical possibility, then Malament-Hogarth spacetimes are not physically possible. I guess this just brings up a certain amount of vagueness in the phrase "physically possible". It is usually taken to mean "possible according to the physical laws", but what exactly delimits what counts as a physical law? Suppose our universe is globally hyperbolic. Would it then be a law that space-time is globally hyperbolic? Anyway, if you have a more restrictive notion of physical law, such that only laws of temporal evolution count, then the laws of general relativity at least appear to permit hypercomputation.
At the end of your post you suggest that the computability of physical law might rule out hypercomputation. But the M-H spacetime argument does not require that the laws are uncomputable. There is a simple argument from the computability of the physical laws to the impossibility of hypercomputation if you assume full determinism, but that is an additional assumption. You can easily prove that hypercompuation is physically impossible if you make the following four assumptions (presented in reverse order of plausibility, according to my own metric):
(1) The laws of physics are computable.
(2) The laws of physics are complete (i.e. there are no phenomena that are not covered by the laws).
(3) Spacetime must be globally hyperbolic (i.e. there must be a space-like surface of the kind described above).
(4) Finite-precision data over any space-like surface is sufficient for accurately determining the data everywhere on that surface's domain of dependence.
Infinite time is not enough to do hypercomputation. You also need infinite memory. If you only have n bits of memory, you only have 2^n possible states, so after time 2^n, your computation must terminate or have entered a loop, so more time is not useful.
Also, your and wikipedia's description is pretty vague. Deutsch proposed a more precise model of computation along a CTC. It assumes that you only have finitely many bits of memory (and thus are computable), but it avoids the problems that shminux mentions. John Watrous and Scott Aaronson proved that in this model, you can take full advantage of the time and compute full PSPACE problems. While such problems are not supposed to be tractable in short time without a CTC, that's a far cry from halting. Also, reversible computing should make PSPACE problems practical in some sense.