Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

First, how i got to the question. I was randomly looking at this page: http://en.wikipedia.org/wiki/Langton%27s_ant

describing some sort of cellular automaton.

Here is the path of this automaton after more then 10000 steps:

Langton's ant trajectory

You can clearly see that after some time ant gets stuck in the loop (actually its a highway) and will be going on it forever.

Here comes the problem with many faces:

If we turn back time and start ant from one of the loop(highway) points we will never get to the original messy part, so obviously this computation is not time reversible since there is no way out of the loop! :) (But there should be ! :D)

Another thing is that information is also not time reversible - since if at some point in computation operation DELETE is used to erase all the previous data there is no way to get that data back.

Ok. So far so good. Lets take this question one step further. How is that so? They always told us laws of physics are time reversible and so on.

My intuitive answer is following. We can say that in the universe there are so called LAWS (physics and so on) and OPERATIONS. What is the difference?

LAWS do not change the objects on which they are operating and hence probably are time reversible.

OPERATIONS on the other hand can change objects, their number in the system and hence are not time reversible (if I delete some files there is no algorithm how to restore them again)

I understand its very close to the idea and interpretation of information.

So when they show us movie backwards and we think time got reversed its actually false! Yes you can reverse the motion of the people and objects, but you can not reverse speach for example since there is no logical connection between phrases being said. Here we can see how the content of the movie (life) is actually twofold - time revesible part (geometry in the poorest sense) and informational part (speech, computations and so on).

From all above it seems that the universe overall is NOT time reversible, and there is no way to go back in time! :) Or is there?

share|improve this question
Have you read the section on Emergent Order in the Wikipedia article you link to? It says that "the ant's trajectory is always unbounded regardless of the initial configuration", which in particular implies that the ant does not get caught in a loop. (It may not be going anywhere very efficiently, but it will eventually excape any bounded region you put it into.) Also: what exactly are you classing as an 'operation' -- would two particles interacting be an operation? But they only interact due to the physical laws. –  Niel de Beaudrap Aug 18 '12 at 12:12
Incidentally, it's not difficult to show that a single computational step of the Langton's Ant automaton is reversible. This is another way of seeing that it cannot get caught in a loop. –  Niel de Beaudrap Aug 18 '12 at 12:14
If we ignore CP violations, are you essentially asking about the Loschmidt paradox? –  Qmechanic Aug 18 '12 at 12:15
As for the ant: yes, it will reach the initial configuration if we reverse time. That is what is meant by "reversible", and the laws of the automaton are demonstrably reversible. Similarly, if you put the ant on a bounded space (rather than an infinite plane), it will eventually reach the initial configuration of the blank plane, because there are only finitely many configurations the CA can take (so it revisits some configuration), and by the reversibility it can only revisit a configuration if it comes by it the same way; so to repeat, it must eventually blank the slate. –  Niel de Beaudrap Aug 18 '12 at 12:39
Finally -- to send a message to someone, you should not put a space between the @ and the name. For instance, you would notify me by writing @NieldeBeaudrap. –  Niel de Beaudrap Aug 18 '12 at 12:42
show 5 more comments

1 Answer

The microscopic laws of physics are reversible or, to say the least, CPT-symmetric (processes are invariant if they're run backwards in time, in mirror, and with antiparticles). The CPT symmetry follows from the Lorentz symmetry.

Langton's ant as well as pretty much any other Turing machine or cellular automaton fails to be microscopically reversible; that's just one reason among many reasons why Langton's ant (or any Turing machine or cellular automaton from the same class) can't be a valid law of physics. It's just a piece of recreational mathematics. Or a model in computer science, if you find recreational mathematics insulting; it's the same thing, anyway.

The physical principles such as microscopic reversibility or CPT-symmetry aren't curiosities or recipes to claim a "paradox" whenever a system of rules violates them. Instead, physical principles are meant to falsify and eliminate proposed rules that fail to satisfy them. So Langton's ant had to be immediately killed as a proposed piece of physics.

Incidentally, while the microscopic laws of physics have to respect the symmetry, emergent laws that deal with incomplete information or, equivalently, ensembles of microstates are irreversible, anyway. That's because the laws of mathematical logic are time-reversal-asymmetric. By definition, the future is a consequence of the past and implication $A\Rightarrow B$ isn't $A$-$B$-symmetric. This basic logical arrow of time is the primary asymmetry that implies all the thermodynamic and related arrows of time.

share|improve this answer
I repeat: Langton's Ant is indeed reversible, and other claims the OP makes about it are also incorrect; not that this affects any of the physics content of your answer. –  Niel de Beaudrap Aug 18 '12 at 16:04
Oh, apologies and thanks. I hope that others will note your correction. Right, the essence of the question would be "if I had a Turing machine that is irreversible", and that's what I was responding to. It should be just a different ant that should be squeezed between fingers. ;-) Well, Langton's ant may still be ruled out as a valid model of physics but not just because of the reversibility condition that it agrees with. –  Luboš Motl Aug 18 '12 at 16:05
@Niel de Beaudrap How is it exactly reversible? If this line is infinite? Anyway i can put out another example a program which gets stuck in the infinite loop. Main claim here is that computational universe is NOT time reversible. And if Mr. Motl can sit at his desk and calculate something that means we are living in a computational universe in a broad sense of this word. –  Asphir Dom Aug 18 '12 at 17:39
@AsphirDom: if you have a single ant, it isn't hard to show. The state of any grid in the cell is given by some pair $(c,d)$ consisting of a colour $c \in \{B,W\}$ for the tile, and a direction $d \in \{0,N,S,E,W\}$ the ant faces (with $0$ being no ant present). Each time-step is a composition of three transformations: a rotation of the ant clockwise or anticlockwise depending on the tile color (which is reversible), a flipping of the tile color (which is reversible), and advancing the ant forward by 1 (which is reversible). The composition of these is also reversible. –  Niel de Beaudrap Aug 18 '12 at 18:12
Check e.g. Feynman's Messenger Lecture on the difference between the past and future. It's focusing on thermodynamics and heat but it derives that the entropy doesn't decrease, kind of, and the logical assumptions are obvious and the time-reversal asymmetry of the very thinking is deeply incorporated into his thinking if you look carefully. It's fundamental. The "Loschmidt paradox" is an overhyped flawed mode of thinking whose incorrectness denies to the wrong assumption that the microscopic T/CPT symmetry is enough for the effective emergent laws to be T-symmetric, too. It's not enough. –  Luboš Motl Aug 19 '12 at 6:05
show 7 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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