When Spacetime Lets You Cheat at Logic

Something you may not have heard of is Malament‑Hogarth spacetimes. Besides sounding like a holographic Yu‑Gi‑Oh card, these spacetimes allow us to compute what we thought was uncomputable. To understand this, we have to talk about what we mean by computable!

The Church‑Turing thesis is often misread as a “theorem,” but it’s more like a claim that “effectively computable” just means “computable by a Turing machine.” To me, it’s more like a definition. It’s also often upgraded to a STRONGER assertion about physics: that no physical process can compute anything a Turing machine can’t. This version (the physical Church‑Turing thesis) is also NOT a theorem. It’s a HYPOTHESIS about the laws of nature.

What If Geometry Could Outrun Logic?

Computability is usually treated as absolute: either a function is computable or it isn’t. But what I found mind‑bending (excuse the pun) is that spacetime curvature actually bends the boundaries of computability itself. Specifically, there exist EXACT solutions to Einstein’s field equations, called the aforementioned Malament‑Hogarth spacetimes, where a computer can complete INFINITELY many steps and (importantly!) report the answer back to you in FINITE time.

Intuitively, imagine this. You hand a laptop to your friend, and they follow a particular trajectory through spacetime… one where, thanks to the geometry, they experience infinite (proper) time. From your perspective, you wait some finite amount of proper time (you age, you get bored, you scroll the internet, all that jazz). But from their perspective, they have forever. Their laptop can run indefinitely. And if all goes well, the result of their computation can still reach you. That’s a big if, but it’s not an “in-principle no.” (though you may want to read my thoughts on how slippery that phrase actually is.)

Infinite Time… But Finite Patience

Why does infinite compute time matter? Because there are classes of problems no Turing machine can solve. The most famous one is the halting problem: given an arbitrary program P and input I, determine whether P(I) halts or runs forever. Turing showed in 1936 that no algorithm exists for this. It’s not that none have found one yet. One provably cannot exist. The proof is something I’ve written about separately, but it’s unnecessary to continue here…

…Anyhow, if your friend’s laptop has infinite (proper) time available, you can just run P(I). If it halts, the laptop fires off a signal: “it halted.” The Malament‑Hogarth structure guarantees that the whole infinite computation lies in your causal past by the time you reach p. This means if no signal has arrived by then, the program doesn’t halt. You’ve just solved the halting problem! And you didn’t even need Scott Aaronson (though having him probably helps).

No algorithmic cleverness here. All it took was you exploiting the causal structure of spacetime. Einstein would be proud, I think.

You’re likely thinking “Curt, are these spacetimes exotic?” Not especially. Certain regions of Reissner‑Nordström (charged black holes) and Kerr (rotating black holes) (specifically, neighborhoods of the inner Cauchy horizon) are actually Malament‑Hogarth. So are cosmological spacetimes constructed by the Budapest school (like Andréka and Németi) that don’t require black holes.

Beyond Turing (somewhat)

The computability‑theoretic consequences are quite wild. There’s something called Recursion Theory which you may know about if you ever read a popular Roger Penrose book. Basically, you can classify sets by the quantifier complexity needed to define them. At the base level, you have the computable (recursive) sets, Δ⁰₁ (what a Turing machine can decide). One level up sit the Σ⁰₁ sets (recursively enumerable but not necessarily decidable) and the Π⁰₁ sets (their complements). The halting set is Σ⁰₁‑complete: the hardest problem a Turing machine can even enumerate, let alone decide! A single M‑H computation lets you DECIDE the halting set. This means you’ve crossed the boundary from Δ⁰₁ into territory a Turing machine provably can’t reach.

Even wilder, which hurts to think about, you can set up nested M‑H solutions where each computes within the causal past of the next. From these you can continue ascending the arithmetic hierarchy, solving problems that sit strictly beyond the reach of any machine at the previous level! Functions that are provably non-computable by any Turing machine become (physically) computable if you embed the computation in the right geometry.

The most fascinating consequences of this are that the boundary between “computable” and “non‑computable” is something I thought was a pure fact of logic. In some sense it is, but when you think about the implementation of this logic into the physical universe, you start to see it as a fact about mathematics plus the structure of spacetime.

Of course, there are catches to this, such as blue‑shifted photons, but the Budapest school has ways around even this. Another issue is that most of these “natural” M‑H spacetimes involve Cauchy horizons (boundaries past which initial data no longer uniquely determine the evolution). I’ve written more about how general relativity strictly speaking isn’t “deterministic” even though we’re often told it is…

…Anyhow, Penrose’s strong cosmic censorship conjecture says that these Cauchy horizons are unstable: small perturbations will cause curvature to blow up. If this is true, then the Kerr and Reissner‑Nordström interiors that host M‑H regions are precisely the regions that nature destroys. The geometry that gives you hypercomputation is the geometry physics won’t let you keep!

Of course, as usual, there’s a catch to the catch! Not all M‑H spacetimes rely on Cauchy horizons. For instance, there are M‑H spacetimes that don’t depend on black‑hole interiors at all but instead exploit large‑scale cosmological structure.

Here’s what’s really going on, as far as I can tell. Many computer scientists treat the physical Church‑Turing thesis as if it were a theorem. The careful ones obviously don’t, but I’ve heard some treat it as fact. An immovable boundary of logic. But it isn’t “fact.” It’s a claim about what the laws of physics permit. The Malament‑Hogarth spacetimes show that general relativity doesn’t obviously respect this claim.

This connects to something deeper. Just as determinism and non‑determinism turn out to be properties of models rather than properties of systems, computability may be model‑dependent too. I need to think about this some more, but it seems like what’s computable depends on the spacetime you’re embedded in. Yes, the mathematical fact hasn’t moved: no algorithm (finite procedure) decides the halting problem. Full stop. In Minkowski spacetime, the halting problem is unsolvable. That’s such a strange phrase even as I type it. Why the heck would a spacetime have anything to do with computability! Well, because in certain Kerr interiors, it doesn’t! A different metric gives you a different answer. What the heck.

---

I want to hear from you in the Substack comment section below. I read each and every response.

—Curt Jaimungal

PS: Please do consider becoming a paying member on this Substack. This is how I earn a living, as I’m directly reader-supported. Moreover, you’ll get a slew of exclusive content such as early access to full podcasts. If you like the free content, you’ll love the members-only content.