Do algorithms have an intrinsic time direction?

Question

This article says

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"?

Answer 1

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.

Answer 2

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.

Answer 3

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.