Computational complexity and time travel

I’ve already put this Scott Aaronson paper in Assorted Links, but here are two passages I liked in particular:

…finding a fixed point might require Nature to solve an astronomically-hard computational problem! To illustrate, consider a science-fiction scenario wherein you go back in time and dictate Shakespeare’s plays to him. Shakespeare thanks you for saving him the effort, publishes verbatim the plays that you dictated, and centuries later the plays come down to you, whereupon you go back in time and dictate them to Shakespeare, etc. Notice that, in contrast to the grandfather paradox, here there is no logical contradiction: the story as we told it is entirely consistent. But most people find the story “paradoxical” anyway. After all, somehow Hamlet gets written, without anyone ever doing the work of writing it! As Deutsch perceptively observed, if there is a “paradox” here, then it is not one of logic but of computational complexity…


Now, some people have asked how such a claim could possibly be consistent with modern physics. For didn’t Einstein teach us that space and time are merely two aspects of the same structure? One immediate answer is that, even within relativity theory, space and time are not interchangeable: space has a positive signature whereas time has a negative signature. In complexity theory, the difference between space and time manifests itself in the straightforward fact that you can reuse the same memory cells over and over, but you can’t reuse the same moments of time.

Yet, as trivial as that observation sounds, it leads to an interesting thought. Suppose that the laws of physics let us travel backwards in time. In such a case, it’s natural to imagine that time would become a “reusable resource” just like space is—and that, as a result, arbitrary PSPACE computations would fall within our grasp. But is that just an idle speculation, or can we rigorously justify it?

It is in general quite an interesting paper.


This does not address the time-travel issue, but what he calls "classical" economics in the paper is not classical economics (or even neoclassical economics).

The Fermi Paradox's "where are they?" query applies to philanthropic time travelers from our distant futures at least as much as it applies to philanthropic aliens from distant reaches of this galaxy or from any other galaxy.

"Time travel", apart from the style we're all accustomed to, apparently never will exist for our descendants, since they're paying us no regular and conspicuous visits from far-flung futures.

It could still exist if it is limited to few actors with limited motivations. The visits could therefore be inconspicuous. One motivation could be their understanding that changing the timeline is impossible, and therefore trying to accomplish things that they know didn't actually happen doesn't succeed. No one likes failure, so they don't try.

I feel compelled to point to a fictional example. You can find it by going to, then under the Category "Loli Stories" you can navigate to the T-W section and click the top link (the title with the C-word in it). However, you should be warned that it is a long-winded science-fiction story with crude language and lots of perverted explicit sex in it. So not for everybody.

Pretty sure shit like that is how you end up on an FBI watchlist. And rightfully so.

You have chosen the fascist state, and you shall suffer in it. And rightfully so.

It could exist, and not induce this paradox, if it is the case that no time travel technology can transport us to any time before the technology is instantiated.


Clearly not true. Take someone back to kill previous himself or his father.

The paradox I was claiming was resolved was not the grandfather paradox, but was the question of why we haven’t been visited from the future.


Time travel is heavily regulated, due to fears of messing with timelines. Given this very rational fear, travel restriction have been imposed so that the only time and places the travelers can visit are those that will make no difference in world events. This means that, in our lifetimes, time travelers are limited to visits to the NFL Pro Bowl, as the stadium is guaranteed to be a place where nothing matters at all.

Are you saying playing the anthem at the NFL Pro Bowl doesn't matter?

I think the best take on time travel in fiction I've ever read limited the travel only to the future due to to natural/physical structure. Future then became conditional on the persons involved -- once you moved some period into the future your next trip had to be even further into the future.

Yeah, because once you introduce a regulation, nobody ever acts contrary to it, forever.

This post simply needed more love.

I wonder how long it would take to go back in time to Shakespeare if we aren't violating speed of light rules. I always thought if we could dislocate in time we'd first be able to dislocate in space so we'd have instant transportation in 3d space before time travel. And if there are no speed of light restrictions, we could blink all over the universe which might be more interesting than going back in time anyway.

I think mathematicians can prove that if the universe has a smallest thing, a chunk of vacuum, then it will have a finite Avogadro's number, the finite number of elements that can be packed into a sphere. Plank's constant seems to indicate the smallest observable thing.

The author is spot on, but the math guys are on it.

Call it a conjecture, here is a hand wave.

If we have a Plank's constant, then Pi is a finite estimation. the implicit assumption being the smallest unit, bound in error by Plank, cannot react fast enough, in the periphery, to get the higher precision Pi needed relative to Big Bang center.

Kinetic and potential energy is the act of doing the computations. If we have Plank, the forces are not infinite.

Here is counter proof. If the compressive forces get large enough, the center can make a smaller Plank's constant. Then the handwave stops we call the pros.

Is this satire?

"the center can make a smaller Plank's constant."
I think he is saying, " the center cannot hold."

"if there is a “paradox” here, then it is not one of logic but of computational complexity."

Or, perhaps it's just a bootstrap problem.

If you like that then you'd probably really enjoy this book written by a physicist turned MIT economist.

Here is most of the book in video format.

I think Trump is the unintended butterfly effect of someone trying to go back in time to fix something completely unrelated to politics.

I think Trump is the only player character in this simulation, and we are just his NPCs. In real life, he's a retiree who bought a copy of "President Simulator", a game that got 6/10 average ratings on the future version of metacritic.

We are randomly generated, and when he's bored of us, we will all disappear forever.

Economists, being economists, are interested in time travel so they can travel backward in time and place their bets on, for example, Bitcoin. But if everyone is capable of time travel, everyone would travel backward in time and invest in Bitcoin, deflating the profits from the investment, thus requiring the time traveler to back further in time, to be replicated by every time traveler, and so on. With time travel, there would be no Bitcoins, just average profits from plain vanilla investments in productive capital rather than unstable markets resulting from highly speculative but otherwise socially useless investments. In other words, equilibrium. Forever.

I don't understand the remark that we can reuse the same memory cells ("space") at different moments of time, but we can't analogously reuse the same moment of time at different spatial coordinates. It seems obvious to me that we can indeed reuse moments of time -- if I have one collection of memory cells at fictional what3words coordinates "house yellow jump" and another similar collection of memory cells at "panther panther hiss", I can perform a computation in the first cells at t = 10, and I can reuse t = 10 to perform a separate computation in the second cells without impacting the first computation at all. How is that different from reusing a single collection of cells at two separate moments of time?

What a waste of time. IF the universe is immutable, then there is *nothing* that says we haven't 'returned' to yesterday a trillion times today - there could be no record of it. If the universe is not immutable, then where is the evidence that future probabilistic events have influenced past actions? There is no credible evidence. The Universe is, arguably, winding down:entropy is increasing, energy is distributing. I'd guess that the amount of energy required to rewind time to some past state is more than sufficient to create a black hole at any location where a 'time travel' machine was turned on, even if we assume it is somehow possible to distribute that energy over the entire (observable) Universe. I vote for not assuming unnecessary facts for which there is no evidence and from which come no testable predictions.

The deep result of Relativity is that the universe is a causal network. A constant maximum speed of causality (aka speed of light) and the warping of spacetime suggest that the causal network is fundamental, and arguably more fundamental than space which might be derivative. Empirically there is zero evidence for causality running backwards in time and the evidence base for Relativity is evidence for this causal structure.

Time travel is both imaginable and interesting, but if you're engaging in a reality-based discussion, forget it.

"In complexity theory, the difference between space and time manifests itself in the straightforward fact that you can reuse the same memory cells over and over, but you can’t reuse the same moments of time."

Seems to be incorrect given the prior example of Shakespeare. Clearly the original moments when Shakespeare originally wrote the plays, in order for one to go back and give them to him is clearly allowing those moments to then be used differently by Shakespeare himself. Not really any different than using the same memory cells or walking, running, sitting, standing, sleeping or a host of other activities on the same physical location.

Part of what's lost in most time travel discussion is the space part. The earth, solar system and milky way are all moving throughout space. If you time travel in even 10 years back, you will arrive in the middle of space and die in a few moments after being exposed to a lack of air and absolute zero temperature.

Comments for this post are closed