= 27d567bc2d48d9f40e9ccc20ea370b15)
V_V 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.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
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.
Even if such spacetimes were possible, in order to exploit them for hypercomptation you would require a true Turing machine with infinite tape, infinite energy supply (unless it was perfectly reversible) and enough durability to run for a literally infinite amount of proper time without breaking. Such requirements seem inconsistent with the known laws of physics.
Why do you believe infinite memory is incompatible with the fundamental laws of physics? In any case, if it is, then Turing machines are physically impossible as well, the only physically possible computational systems are finite state automata, and there is no halting problem. You are right that in this case the infinite run-time provided by M-H spacetimes will not give any computational advantage, since every finite state machine either halts or loops anyway. But in discussions of computability theory I always assume that we are idealizing away memory constraints (unless explicitly stated otherwise).
As for the infinite energy requirement, there are three things to say. First, a Turing machine with infinite tape does not need to perform any irreversible computations (such as erasure). Second, even if it does perform computationally irreversible steps, this does not mean they are thermodynamically irreversible unless the Second Law of Thermodynamics holds, and this is not a fundamental law of physics (see this comment). Third, even if infinite energy is required, I don't think the assumption of an infinite energy source is incompatible with any of the fundamental laws of physics.
The durability concern also seems to depend on thermodynamic considerations, although perhaps there is some genuine inconsistency with fundamental law here once quantum mechanics enters the picture.
Well, an infinite memory store or an infinite energy source would have infinite mass. So it would either take up the entire universe and have nowhere external to send its results to or, if it had finite size, it would be inside its own Schwarzchild radius, and there would be no way to send a signal out through its event horizon.
So yeah, I'd call infinite storage or power sources (as politely as possible) "unphysical".
And I don't see why you think the halting problem goes away just because you can't put infinite tape in your Turing machine, or because you use finite state automata instead. You still can't set an upper bound on the size of computation needed to determine whether any algorithm in general will terminate, and I kind of thought the point of the halting problem was that it doesn't only apply to actual Turing machines.
These are not the only options. Infinite sets have infinite proper subsets, so an object in a spatially infinite universe could have infinite size without taking up the entire universe. In a universe with an infinite amount of matter, a computational process could requisition an infinite proper subset of that matter as memory while still leaving plenty of matter to build other stuff. Or (if you don't take the cosmic censorship hypothesis as a constraint on physical possibility) you could have a naked singularity functioning as a white hole (the time reverse of a black hole, allowed by the time reversal invariant Einstein Field Equations) disgorging matter as needed for the computation.
That said, I am concerned about the fact that making the computational device too large would significantly modify the background metric, so (as shminux pointed out) one can't glibly consider a M-H spacetime, put a massive (perhaps infinitely large) Turing machine in it, and still assume that it is the same spacetime. It's not obvious to me that it would be impossible to have a device of this sort in an M-H spacetime, but neither is it obvious that it would be possible (and FWIW, I would bet against the possibility).
I think the right response is that infinite memory is always an idealization in discussions of computability. When we talk about the Church-Turing thesis as limning the notion of "computable", we are ignoring spatial constraints. Computability is a pure mathematical concept, not an engineering concept. When a theorist says that X is computable, she is not committing herself to the claim that the universe contains physical resources sufficient for the construction of a computer that implements X. Why should this usual standard become more rigid when we consider M-H spacetimes?
Every finite state machine will either halt or start repeating itself in finite time. This is guaranteed. To figure out whether a particular machine halts, simply wait until it either halts or enters a state it has entered before. One of these will happen within finite time, so you will always be able to determine within finite time whether or not the machine halts. It's true that if you want a single halting oracle that works for finite state machines of arbitrary size, it cannot itself be a finite state machine, it would have to be a Turing machine. Is this what you mean by the halting problem for FSAs? If so, then I agree, but that is a different sort of problem from the halting problem for Turing machines. My point was just that in the case of FSA's (unlike Turing machines) there's no computation that is ruled out solely due to the lack of infinite runtime; allowing infinite runtime doesn't increase the power of FSAs.