# Do algorithms have an intrinsic time direction?

There is no intrinsic time direction in Newton's mechanics nor in the differential equations of the new physics.

My question is, do other types of mathematics, say a cellular automata as an example, have the intrinsic time direction that the equations lack?

With a CA, all steps have to be completed sequentially.

UPDATE: Here's what I mean. On this page, it describes projectile motion. It uses one approach with equations, and another approach with an algorithm. Very clearly both approaches yield the same answers. The biggest difference between them is how time works.

Question:

Is having "an intrinsic time direction" the same thing as "time having no choice but to march forward in the algorithm"?

• – Kyle Kanos Dec 13 '13 at 19:50
• Closed because I made an original (apparently) argument against time travel using mathematics. So I am focusing just on mainstream physics this time. – MikeHelland Dec 13 '13 at 19:55
• I will repeat my comment on the previous questions. Contrary to the quote in the question, microscopic physics is not time reversal invariant anymore. The cases where the violation occurs are pretty esoteric, and they don't add up to enough violation to explain the baryon asymmetry, but they are down there at the root of the observed behavior of the universe. – dmckee --- ex-moderator kitten Dec 13 '13 at 20:21
• I'm confused... You're looking for equations that are time invarient but algorithms to solve them that are not? Virtually any finite difference, volume, or element discretization is not "reversible" -- if you march forward one step then backwards one step, you don't get the original answer due to truncation errors. – tpg2114 Dec 13 '13 at 20:36
• I'm not looking for equations. My question was in response to reading about the intrinsic direction of time, and wanting to know if algorithms or simple programs like cellular automata have an intrinsic time direction. – MikeHelland Dec 13 '13 at 20:49

I'll concentrate on cellular automata in this answer, because it's a good example, and should help to give a good intuition about algorithms in general.

The answer is: most cellular automata do have an intrinsic time direction, but some don't.

The most famous example of a cellular automaton is John Conway's Game of Life. This is an irreversible cellular automaton: it has a definite direction of time, in the sense that you can't run it backwards. Running it forward is easy: every cell gets turned on or off according to definite rules that depend on its state and the state of its neighbours. But in reverse this doesn't always work. For example, suppose that at time $t$, some particular cell is off, and all its neighbours are also off. Was this cell on or off at time $t-1$? There is no way to know. If it had been on in the last time step, it would be off now, because all its neighbours are off - but if it had been off then, it would also still be off now. So there's no reverse version of the algorithm. It loses information as it runs.

But this is not the case for all cellular automata. There are "reversible" ones, where you can always work out the previous state. My favorite example is called Critters, although there isn't much information about it online. (If you're prepared for an in-depth read, there's a nice paper that describes it.) Reversible cellular automata have some interesting properties. For example, if two gliders collide, at least one glider must emerge from the resulting debris. If it didn't, the debris would eventually go into a cycle (exactly repeating one of its previous states) and then you'd lose the information about when the glider collision occurred. Since a reversible cellular automata can be run "backwards" from its final state to its initial state, there's a sense in which it doesn't have an intrinsic direction of time.

There are analogues of all this in the wider world of algorithms. There are a lot of known techniques for constructing reversible algorithms, collectively known as reversible computing. This is quite an important area of computational theory, because the theory of quantum computing builds upon it.

• My question was about "intrinsic time direction" and the answers are about "reversibility". It seems the two concepts are intertwined. I think maybe my question is really: do they have to be? The algorithm in the webpage (2nd link) could be modified to run backwards, but that would only prove you could modify it so t=t-1 instead of t=t+1 which I don't think really proves anything. Is reversibility a moot point when the algorithm says t=t+1? – MikeHelland Dec 20 '13 at 17:54

I'm not entirely sure I understand what you're asking but here is how I've interpreted your question:

It seems like all of the laws of physics are reversible in time. That is, given the state of a physical system, it's possible to both go forward in time or backwards in time from that state. Assuming this is the case for physical laws and the equations that govern them, are there algorithms and mathematical processes that don't have this reversible property?

If this is your question then it's a computer science / math question and not a physics question but the answer is simple so here goes: yes.

It comes down to whether the algorithm destroys information or not. Take a very simple function like $\operatorname{AND}$:

$$0 \wedge 0 \rightarrow 0$$ $$0 \wedge 1 \rightarrow 0$$ $$1 \wedge 0 \rightarrow 0$$ $$1 \wedge 1 \rightarrow 1$$

As you can see, this destroys information. Given the output $0$ the input could have been $(0,0), (0,1), (1,0)$ which means $\operatorname{AND}$ is not reversible (information was destroyed).

In general, for a function (or algorithm) to be reversible it needs to be an injection. If you want every state of output to map to another state of input and for the mapping (function / algorithm) to be reversible it needs to be a bijection.

My question is, do other types of mathematics, say a cellular automata as an example, have the intrinsic time direction that the equations lack? With a CA, all steps have to be completed sequentially.

A reversible system is not related to whether it is differential equation, algorithm or cellular automata. It is the underlying model, or physics, determine whether it is reversible.

Physics at the microscopic level are most reversible, but with some exception mentioned in the comments. The equation describing macroscopic system are in contrast usually not reversible. It is similar for CA, in which most of them are not reversible but some are.

To determine reversibility, for the differential equation, you can check whether $t\to -t$ symmetry preserve. For CA, you can check whether the rules preserve local symmetry. It has nothing to whether the steps is completed sequentially.

Is having "an intrinsic time direction" the same thing as "time having no choice but to march forward in the algorithm"?

The intrinsic time direction is better defined by the following: For a given model, when you go forward in time and then go backward in time to the original point, whether you can still have the same state? If yes, then it is reversible. Otherwise, you can say that time have a direction, and the direction is defined by which entropy increase.

• You say "and then go backward in time". With t as a dimension in an equation that makes some sense. In an algorithm where each step is calculated from the previous state does that definition still work? – MikeHelland Dec 20 '13 at 17:59
• @mikethematrix Yes, what you called algorithm is basically a numerical method called finite different of the Newton's second law. The terms are not written explicit there ball.t = ball.t + dt and you should include it into other term which will let you move back in time if you use -dt instead. For the algorithm shown in the page, the easiest way to revert is to change $v\to -v$ – unsym Dec 20 '13 at 20:09
• @mikethematrix Regarding about the intrinsic and reversibility, it is determine by the viewpoint of the person stay inside the "algorithm" (i.e. universe). NOT by the person who run the program outside running it, which may or may not have be one direction. As long as everything is reversible inside the simulation, then there is no "intrinsic" time direction. – unsym Dec 20 '13 at 20:11
• Use -dt instead? You would be changing the algorithm then. You would have two algorithms, the original and the -dt one. To go backwards in time doesnt require the equation to change, just operated differently. Doesn't the fact a single equation can go either direction but the algorithm can't (unless you create a new algorithm) give the algorithm an intrinsic time direction? Also, is there any literature that supports the validity of using an observer "inside" the algorithm rather than outside it? – MikeHelland Dec 21 '13 at 1:44
• @mikethematrix To "move back" in time, you actually do the same thing in both situations, i.e. $dt\to -dt$. Then when you INCREASE the time as external observer, you are essentially going back. You don't need a literature in any case, the key point is what is your focus. We live inside the universe, so we are talking anything inside it – unsym Dec 21 '13 at 3:58