Can somebody explain this to me?: The computability of the laws of physics and hypercomputation

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.

is there any chance it's possible to build a physical device that answers questions a Turing machine cannot answer?

I don't think computability is the right framework to think about this question. Mostly this is because, for somewhat silly reasons, there exists a Turing machine that answers any fixed finite sequence of questions. It's just the Turing machine which prints out the answers to those questions. "But which Turing machine is that?" Dunno, this is an existence proof. But the point is that you can't just say "you can't build a device that solves the halting problem" because, for any fixed finite set of Turing machines, you can trivially build such a device, you just can't recognize it once you've built it...

It follows that in the framework of computability, to distinguish a "real halting oracle" from a rock with stuff scribbled on it, you need to ask infinitely many questions. And that's pretty hard to do.

So I think the correct framework for thinking about this problem is not computability theory but complexity theory. And here it genuinely is an open problem whether, for example, it's possible to build a physical computer capable of solving some problems efficiently that a classical computer can't (e.g. a quantum computer). Scott Aaronson has written about this subject; see, for example, NP-complete problems and Physical Reality as well as Closed Timelike Curves Make Quantum and Classical Computing Equivalent.

In the framework of complexity theory, one can now also ask the following question: if someone built a device and claimed that it could solve some problems more efficiently than our devices can, how do we efficiently verify that their answers are right? This question is addressed by, for example, the framework of interactive proofs. As Scott Aaronson says, this allows us to make statements like the following:

We now know that, if an alien with enormous computational powers came to Earth, it could prove to us whether White or Black has the winning strategy in chess. To be convinced of the proof, we would not have to trust the alien or its exotic technology, and we would not have to spend billions of years analyzing one move sequence after another. We’d simply have to engage in a short conversation with the alien about the sums of certain polynomials over finite fields.

Edit: I should clarify that when I said

here it genuinely is an open problem whether, for example, it's possible to build a physical computer capable of solving some problems efficiently that a classical computer can't (e.g. a quantum computer).

there are actually two open problems here, one practical and one theoretical. The practical question is whether you can build quantum computers (and physics is relevant to this question). The theoretical question is whether a quantum computer, if you could build one, actually lets you solve more problems efficiently than you could with a classical computer; this is the question of whether P = BQP.

You've discovered for yourself that hypercomputation is a cottage industry of dubious and contrived articles that often seem to dress conceptual misunderstandings as computational models. Computability is not by itself a diseased discipline (to use a convenient phrase from the LW stock), but hypercomputation, I feel, is a diseased little subfield within it.

Your characterization of critiques of hypercomputation as too specific is, I think, a little unfair. Most (I hesitate to say all - haven't thought about this in many years) HC proposals I've seen fall into one of these two camps:

1. Miraculous access to infinite precision.
2. Miraculous access to infinite time.

Martin Davis's article, to which you link, seems to me to do a good job of doing away with all of the first category.

You ask if there's a general critique of hypercomputation that works against all proposals, along the lines, for example, of showing that it'd require infinite-precision measurements. I don't think that can work, because, after all, it's not inconceivable that the Church-Turing Thesis is false; I don't believe that there's agreement that it stands proved or even provable (some would disagree). Perhaps there's a plain-old-boring way to hypercompute without whimsical GR models or miraculous oracles, but just by doing something with normal and finite resources that the Turing machine model somehow overlooked; that would be hypercomputation, and I don't know how to rule that out.

Is there a general critique of most or all published "fancy" hypercomputation proposals, from both 1. and 2. above? I don't know of anything published (but again, it's been many years since I actively thought about and sought out this material). I have some thoughts that may persuade you partially, or maybe not. I'm sure they wouldn't persuade most HC enthusiasts. I wanted once to write them up for a short essay or article, but never did (at least so far). Here's a very short summary.

The idea is that we're seduced by HC ideas because we fail to define clearly three things:

• what is computation as a mathematical model
• what is computation as a physical process
• why do we trust the results of computation as a physical process

As a thought hypothesis, consider a Pentium CPU with a floating-point division bug (google for details if not familiar). The bug was discovered by a mathematician puzzled at weird-looking division results. Normally we trust without questioning that our computers perform division accurately. Most of us treat our computers or calculators as black boxes that somehow manage to compute the right results (almost nobody knows the actual division algorithm implemented inside the CPU). Yet for some reason, when the mathematician found a discrepancy between the CPU performing the division and, say, a verification by hand, and validated a discrepancy with a few repeats, they must have immediately understood that the CPU is at fault, rather than the familiar long division algorithm is at fault. The CPU normally divides much faster and much more accurately then we can by hand; why didn't it even occur to the mathematician that maybe it's a bug in the long division algorithm rather than the one in the CPU? The reason is that the mathematician doesn't actually trust the CPU; they trust the algorithm of dividing two numbers, and they trust, to a lesser degree, that the CPU accurately implements the algorithm, and they trust, to a lesser degree, that there are no physical faults, cosmic rays, etc. etc. screwing up the implementation.

This and similar thought experiments may convince you that when we have a physical device doing something, and then we interpret its results (e.g. photons coming from monitor surface to your eyes) in a particular way as a result of a computation, there're two different kinds of trust that we invest the process with: say, mathematical trust and physical trust. For mathematical trust to exist, there must be a mathematical model, an algorithm, which we may comprehend and make sense of completely mentally, and then physical trust is the degree to which we believe the physical device accurately implements that mathematical model. I propose that without the existence of this wholly mental mathematical model (often implicit existence that we take on faith) we're not actually justified in calling the whole thing "computation", and the bulk of the trust that we put in its results evaporates.

There seem to be some limitations on how this mental mathematical model might work; for example, some notions of discreteness and finite computational time seem required for us to comprehend the model. These may be limitations of our mind; but our notion of computation, I claim, is intrinsically linked with what our minds are capable of. If we can make explicit these bounds on how our mental mathematical models may look like, that, to me, seems our best hope of "proving" the Church-Turing Thesis.

All the hypercomputation proposals, both from category 1. and 2. above, break this correspondence between a comprehendable (in principle) mental mathematical model and a physical realization, and instead depend in one crucial way or another on some physical thing as a non-abstractable step in the process. Just as with infinite precision proposals you wouldn't actually know where to get those arbitrary-precision decimals of a noncomputable real number in your mind, with the infinite time proposals you wouldn't know how to perform an infinite Turing machine run in your mind. Therefore, I claim, though on the surface these hypothetical devices look just like CPUs and calculators, albeit very exotic ones, in reality they are very different, and should not be called computational devices, do not deserve the trust we put in computational devices. This lack of trust can also be demonstrated, usually, by thought experiments that involve verification or validation. E.g. say you have an exotic GR model that lets you do an infinite TM run in some place and send a signal back to you during the run if the machine stopped, etc. Say you didn't get a signal. How do you know that the machine never stopped, as opposed to something going physically wrong with the machine, the signal getting lost on the way etc.? You may retort, but how do you know that there wasn't a cosmic ray in the CPU when it divided etc., but there's a difference. With the CPU there's a mental model which gets the bulk of your trust, and you only trust the atoms of matter insofar as they correspond to it. If the atoms should fail you, nevermind, you'll find other atoms that work better, the model is intact. With the GR hypercomputation, you have to trust the signal ray itself, trust the atoms rather than the bits in your mind. I don't think we'd be justified in doing that.

(Quantum computation is wholly exempt from this reasoning; from computability's point of view, it's just a nifty implementation trick to construct a physical device that executes some particular very well-defined mental algorithms in a massively parallel way, achieving a vast speedup).

is there any chance it's possible to build a physical device that answers questions a Turing machine cannot answer?

Since any finite set is trivially computable, it only makes sense to talk about hypercomputation for infinite sets/functions. For example, a certain kind of infinite time Turing machine can solve the halting problem of every other finite time Turing machine.
This would mean that to physically realize a hypercomputer the universe has to allow finite access to infinite quantity (e. g. an infinite precision measurable real value, an infinite time pocket universe, etc). There are highly idealized model that does such things in both newtonian mechanics and general relativity, but they are not applicable to our universe.
Hypercomputation is a (set of) well defined mathematical model(s), so the question of its realizability is ultimately a physical one: at the present time knowledge we have about our universe rules out such models, but of course we cannot show that this continues to be valid in possible extensions.

When building the physical device, is the Turing Machine it is required to beat also required to have a potential physical instance in the observable universe?

What I mean is, if there are (A) atoms in the observable universe, and I think of a type of question that would provably take a Turing Machine at least (10A) atoms to answer, and then build a Non-Turing Machine that answers those questions in only 1 million atoms, then a Hypothetical Turing Machine could answer the question, but no Physical Turing Machine made of (10A) atoms could be found in the observable Universe.

However, I'm not sure if this falls into the bounds of the sexed up mistakes you are referring to above, or if it doesn't.

Some of the ways to convince yourself that "hypercomputation" might be physically possible seem like obvious confusions, for example if you convince yourself that some physical quality is allowed to be any real number, and then notice that because some reals are non-computable, you say to yourself that if only we could measure such a non-computable quantity then we could answer questions no Turing machine could answer. Of course, the idea of doing such a measurement is physically implausible even if you could find a non-computable physical quantity in the first place.

So what you're claiming is that there is an absolute limit to the precision with which any physical constant can be measured.

It seems like it might be possible to make such an argument; I've read that the laws of physics are consiered to be computable, but I don't have a good enough understanding of what that means to tell if it entails that hypercomputation is physically impossible.

The laws of physics as we understand them appear to be computable (baring issues with knowing constants to infinite precision), but our understanding of the laws is incomplete. Firstly no one has been able to reconcile GR and QM. Furthermore, how do we know our understanding of the laws of physics isn't merely an approximation to the true laws, like Newtonian mechanics is an approximation to relativity?

It seems like you can go beyond Turing machines long as you're willing to take the output in the form of something a Turing machine cannot output. But "let's measure this physical system and then write down some finite-length numbers" is still numbers, something a Turing machine can do. Instead, a physical hypercomputer can have super-Turing precision at stuff like "take these input voltages and give me an output voltage."

The Turing model is pretty outdated, and doesn't really describe everything modern computers do.

However - you can run a simulation of a modern computer inside the Turing model (essentially running an interpreted, rather than compiled, language). Which means, very roughly, that any problems that are provably undecidable in the Turing model are necessarily undecidable in the RASP model.

In order to exceed the limitations of the Turing model, it isn't sufficient to be able to do things Turing computers can't; you must be capable of doing things Turing computers can't even simulate. An additional hardware logic gate doesn't cut it, if you can create the same logic by mixing existing logic gates. You have to create logic which cannot be described in existing logic systems. (If anybody wants to try this, good luck. The -thought- makes my brain hurt.)

Note that the proposed solution for, for example, the Halting Problem is not in fact solving something that Turing computers can't, as the solution is effectively to run a turing algorithm for an infinite number of steps. It's taking out one of the assumptions that went into the proof, that you don't -get- an infinite number of steps. And if anybody is taking this seriously, I pose a question: What happens when the cardinality of the infinite operations to solve the problem is greater than the cardinality of the the infinite time spent solving that problem?

ETA: -6? Seriously? I'm not sure exactly what's being downvoted here, but I assume it's my comment that the Turing model is outdated. Well, it is. Not going to apologize for it; computers haven't even vaguely resembled its common-memory-model in decades, and we regularly run algorithms which are far more efficient than the Turing model allows. Even RASP is hopelessly outdated at this point, but it is at least closer to what computers are actually doing. Given that the Church-Turing thesis has not in fact been proven (largely because those trying to prove it gave up on trying to define what exactly it meant), the Turing model largely persists because of its simplicity.