There are relativistic spacetimes (e.g. M-H spacetimes; see Hogarth 1994) where a worldline of infinite duration can be contained in the past of a finite observer. This means that a normal observer can have access to an infinite number of a computation steps.

Assuming it's possible for a computer to functional perfectly for an infinite length of time (and I know that's a big ask): one could construct a computer HM which travels along this infinite worldline, computing the halting problem for a given M. If M halts, HM sends a signal to the finite observer. If after an infinite number of steps the observer doesn't get a signal, the observer knows that M loops, solving the halting problem.

So far, this sounds okay to me. My question is: if what I've said so far is correct, how does this alter Turing's proof that the halting problem is undecidable? Why does his proof fail in these spacetimes?

  • $\begingroup$ Maybe relevant: researchgate.net/publication/…. $\endgroup$ – Martín-Blas Pérez Pinilla Apr 6 '18 at 18:21
  • 1
    $\begingroup$ Will the infinite duration observer have access to infinite energy to perform its infinite computation steps? (alternatively, can a halting problem tester be formulated in a reversible way? I wouldn't think so) $\endgroup$ – user253751 Apr 7 '18 at 0:19
  • $\begingroup$ Definitely relevant: chiark.greenend.org.uk/~sgtatham/infinity.html $\endgroup$ – Jules Apr 7 '18 at 14:01
  • $\begingroup$ @immibis: Yes it does! I studied this in college. $\endgroup$ – Joshua Apr 8 '18 at 3:54
  • $\begingroup$ Note that it is a common misconception that a turing machine that does not halt must “loop”. This implies a sort of repeated state, or of doing the same thing over and over again. In fact we can decidably tell whether a machine has this behavior or halts given it does one of the two. The troublesome machines that mess us up aren’t the looping ones, but rather the ones that chaotically whirl off in an almost random pattern, defying all sense of regularity. $\endgroup$ – exfret Feb 18 '19 at 19:58

Note that Turing's proof is one of mathematics, not of physics. Within the model of a Turing machine Turing defined, undecidability of the halting problem has been proven and is a mathematical fact. Hence, Turing's proof will not 'fail' in the spacetimes, it will simply not prove anything about the relation of the halting problem and time dilation.

However, what you'll likely want to know is whether a 'time dilation Turing machine' can solve the halting problem.

If you want to study this the influence of 'time dilation' on a Turing machine, you'll have to specify a formal model by which we can formally understand what it means for a Turing machine to make use of time dilation. Unfortunately, this format is ill-suited for providing such a formal model (unless someone else has written a paper about it) as creating the model is far too broad.

However, it isn't unlikely that some formalisation indeed is able to solve the halting problem. This paper by Scott Aaronson, Mohammad Bavarian and Giulio Gueltrini looks at computational models under the assumption that so-called Closed time-like loops exist and conclude that the halting problem is indeed computable within that model.

  • 4
    $\begingroup$ Perhaps also useful is that the formalism of a "hyper-turing-machine" as a Turong machine that can do an infinite number of steps in a finite amount of time is indeed a common formalism. You may find a lot of useful material there. $\endgroup$ – Cort Ammon Apr 6 '18 at 22:13

The Turing machine is a formal mathematical model of computation, it does not answer to any physical limitations and does not care about relativistic effects. This means that Turing's proof does not fail, since the standard definition of Turing machine does not even contain a notion of "spacetime".

What you can try and do, is to define a different model of computation inspired by relativity. Again, this will only be a formal object, and the question of whether it can or can't solve the halting problem belongs to the realm of mathematics and depends on your specific definition. However, the true question now is whether this new model indeed correctly captures relativistic effects, i.e. does it really reflect our physics and can be implemented in our world?

You can see such a discussion regarding quantum computation. We have a formal definition of "quantum Turing machines", and their exact computational power remains an open problem in mathematics (not even close to the halting problem though). Still, you can argue that this definition does not really reflect our understanding of quantum physics, and a better one is needed. There are arguments that suggests that such machines cannot even be built, so their exact power has no effect on the (strong) Church-Turing thesis.

Back to your question. There is a formal notion of an infinite time Turing machine, but in order for it to have any effect on the Church-Turing thesis you need it to exist in practice. You might be interested in Scott's paper, which has a section about computations utilizing relativistic effects, though it seems that naive arguments are hopeless (in the sense that they are impractical, as time cost is replaced by energy cost).

  • 1
    $\begingroup$ Re. "... in order for it to have any effect on the Church-Turing thesis you need it to exist in practice." - aren't Turing machines also idealised machines which can't exist in practise? $\endgroup$ – daisy Apr 6 '18 at 13:09
  • 1
    $\begingroup$ Indeed, it only reflects (or at least attempts to) our intuition regarding what is a "computing machine". This is why the Church-Turing thesis is a thesis, and not a mathematical theorem. It only informally claims that Turing machines capture the true computational power which exists in our world. $\endgroup$ – Ariel Apr 6 '18 at 13:20
  • $\begingroup$ My point is: why must an infinite time Turing machine exist in practise for it to have any effect on CTT, when standard Turing machines don't exist in practise either? $\endgroup$ – daisy Apr 6 '18 at 13:23
  • 1
    $\begingroup$ One formulation of the Church-Turing thesis is the following: every possible computational model realizable in our world does not exceed the power of the Turing machine. The thesis itself is defined relative to some ground model (namely, the Turing machine). $\endgroup$ – Ariel Apr 6 '18 at 14:08
  • $\begingroup$ I asked a followup question because even after going over the posted slides I don't really understand the claim that a practical quantum Turing machine cannot be built. (2nd time to post this comment, now points to QC.SE instead of CS.SE) $\endgroup$ – BurnsBA Apr 6 '18 at 16:37

Turing’s proof shows that no Turing machine can solve the Halting Problem no matter how much time you give it. If your spaceship used time dilation to give a computer a billion years to work, it still might not be able to tell you anything more definite than, “Not yet.”

Apparently, (Thanks, @DiscreteLizard!) if you have time travel that cannot cause paradoxes, you could set up a time loop that would cause a paradox if the computer cannot prove whether the Turing machine halts. Either it receives the answer from the future and transmits it back to itself, or it runs forever (and, cleverly, returns a quantum superposition that resolves to a stable time loop). But, before you try this, be very very sure that it’s safe to cause a time-travel paradox.

  • 2
    $\begingroup$ "There is as yet insufficient data for a meaningful answer." $\endgroup$ – Robert Columbia Apr 7 '18 at 4:20
  • $\begingroup$ Note that the main reason why I mentioned Turing machines under closed time-like loops is that there exist some 'physical modification' of the Turing machine model such that the halting problem is computable by that machine. It seems that others know more about time dilation than me, but this example makes me at least hesitant to make such claims unless a formalization of time dilation is given. $\endgroup$ – Discrete lizard Apr 7 '18 at 8:50
  • $\begingroup$ @Discretelizard That was a great contribution to the discussion. I’m not sure I completely understand the OP’s intent, but relativistic time dilation is a real concept in modern physics, and I answered on the assumption that he was using the standard definition of the term. $\endgroup$ – Davislor Apr 7 '18 at 19:38
  • $\begingroup$ @Davislor Of course time dilation is well defined, within physics. A Turing machine is a mathematical object. As far as I'm aware, the best we can do to combine the two is to create a 'physical analogy' of a Turing machine might be and formally show how this interacts with time dilation. This is (an example of) what I mean with a 'formalization'. I don't think there is an unique way to formalise this and that the results may differ, hence my hesitation to say anything conclusive about it. $\endgroup$ – Discrete lizard Apr 7 '18 at 20:38
  • $\begingroup$ That said, it could be possible that the answer is 'no' for any reasonable formalistation, but such a claim is beyond my expertise, at least. $\endgroup$ – Discrete lizard Apr 7 '18 at 20:38

An objection is that you have defined a process that can produce infinite entropy in a compact region and that appears to do so in a finite segment of the observer's past. This means a few things

  • The computational entropy in the compact region exceeds the Bekenstein bound on entropy (which bound is proportional to the surface area of the region), so it collapses into a black hole (instantly) and no signal can ever reach you from its interior. (The Kerr metric describes an M-H spacetime. The infinite process is only observed to complete as the observer passes into the inner event horizon. Disregarding the current uncertainty about the physics of such passage, no remote observer ever has access to the result of the computation -- only the observer who has vanished into the black hole has the result. This is not a description of a useful computational process. To paraphrase: "We have an oracle that produces the correct answer to any question you ask in constant time in such a way that the answer exists only at the instant it is destroyed by flushing it down a black hole.")
  • A Turing machine destroys information every time it overwrites a symbol on a tape, so by Landauer's principle, a finite computation on an infinite world line compressed into a finite segment in the past light cone of the observe must be observed to require infinite power and emit infinite heat during the infinitesimal time it is observed to operate. That is, since a halt is achieved in finite time, it is achieved instantly from the point of view of the external observer, so all the power is consumed instantly and all the heat is evolved instantly. Alternatively, if the computation does not halt, the compact region continuously consumes infinite power and emits infinite heat. Net result: a black hole, again.
  • Alternatively, the Landauer principle does not apply to reversible computing and there are (universal) reversible Turing machines. However, such a Turing machine requires the ability to represent the entire space of potential computational states, which is exponential in the size of the amount of tape used, so quickly runs into the Bekenstein bound. We end up being able to avoid the heat problem only by restricting to bounded-length tapes. Equivalently, we have an upper bound on usable tape length controlled by the surface area of the region that has an infinite worldline. If you don't account for this and your computation uses too much tape, you get a black hole, again.

It is an interesting open question whether and how these constraints apply to quantum computers. It may well be that the complexity of a computation performable by a quantum computer is limited by the surface area of the computer. So we may have to double the surface area of an extremal quantum computer to get one more usable qubit of computation. This quickly leads to impractically large computers.


Quote from Bangs, Crunches, Whimpers, and Shrieks:

Thomson lamps, super $\pi$ machines, and Platonist computers are playthings of philosophers; they are able to survive only in the hothouse atmosphere of philosophy journals. In the end, M—H spacetimes and the supertasks they underwrite may similarly prove to be recreational fictions for general relativists with nothing better to do. But in order to arrive at this latter position requires that one first resolve some of the deepest foundation problems in classical general relativity, including the nature of singularities and the fate of cosmic censorship. It is this connection to real problems in physics that makes them worthy of discussion.
There are also connections to the philosophy of mathematics and to the theory of computability. Because of finitist scruples, some philosophers have doubted that it is meaningful to assign a truth value to a formula of arithmetic of the form $(\exists x_1)(\exists x_2)\dots(\exists x_n)F(x_l,x_2,\dots,x_n)$. It seems to me unattractive to make the truth of mathematical statements depend on the contingencies of spacetime structure. The sorts of arrangements considered above can be used to decide the truth value of assertions of arithmetic with a prenex normal form that is purely existential or purely universal. (Fermat's last theorem, for example, has a purely universal form.) For such an assertion $\gamma_1$ is set to work to check through the (countably infinite) list of $n$-tuples of numbers in search of a falsifier or a verifier according as the assertion to be tested is universal or existential, and $\gamma_1$ reaps from these labors a knowledge of the truth value of the assertion. But as soon as mixed quantifiers are involved, the method fails. However, Hogarth (1994) has shown how more complicated arrangements in general relativistic spacetimes can in principle be used to check the truth value of any arithmetic assertion of arbitrary quantificational complexity. Within such a spacetime it is hard to see how to maintain the attitude that we do not have a clear notion of truth in arithmetic.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.