​

Abstract

In this work, we study mobile automata, discovering a theorem that fully characterizes their reversibility. We outline the proof and verify these results through computations. We also provide background on how the proof was discovered. By examining their behaviors, we identified reversible mobile automata exhibiting seemingly unpredictable behavior. When restricted to a finite cyclic tape, we found that all reversible automata form closed cycles.

What are Mobile Automata?

Mobile automata are a variant of automata in which only a subset of cells around an active cell, which we will call the ‘head’ of the MA, are updated at each step. In the diagram below, the red line indicates how the ‘head’ of the mobile automaton moves, while the black lines show which cells are changed. This is a single step taken by the mobile automata.
Out[]=
The state isn’t limited to any number of cells, below would also be a valid state. The head is at value 6, and the state is a sequence of colors.
Out[]=
Repeating this, we see the system evolve over time. This diagram shows the first 20 steps of an MA.
Out[]=
Cells can be colored an arbitrary amount of colours, and as we add more colours we get exponentially more rules as we will need rules for many more input states. We say a MA has rules from
n
odd cells to
n
odd cells of
k
colours. Here are some examples of different sets of rules. For
n3k2
I can fit them, however for larger
n
and
k
I am not able to fit them all into the diagram.
Out[]=
n=3 k=2
n=3 k=3
n=5, k=2
​
In general, for a MA from
n
odd cells to
n
cells of
k
colours, we have
n
k
inputs to consider.

AS Theorem

We know that mobile automata are able to move the head in both direction. To have a more accurate grasp on the rules we are discussing, we shall introduce some naming conventions for them. They will become necessary to understand once we go into the proof.
L-rules move the head to the left.
R-rules move the head to the right
The blocker of a rule is the
n
-2
cells of the output cells in the direction the rule moves, centered around the head
Below we have all 3 definitions visualised.
Out[]=
An L-rule
An R-rule
Blocker for an L-rule
Blocker for an R-rule
We call a set of rules reversible if and only if for every state
S
there exists a unique ancestor
′
S
such that
M(
′
S
)S
A
n
to
n
Mobile Automaton
M
with
k
colours is reversible if and only if either
1
.
The rules move the head towards only one direction, and all rules have unique outputs
2
.
The rules move the head in both directions with the properties
2
.
1
.
The R-rules have unique outputs among themselves.
2
.
2
.
The L-rules have unique outputs among themselves.
2
.
3
.
The R rules and the L rules have different blockers.

AS Proof Outline

This section describes a short outline for the proof.
​
We shall do a case by case analysis for all
n
to
n
Mobile Automata of
k
colours.
Let
S
be any state. We will impose conditions on the rules that will determine the number of possible previous states of
S
, and show that under our conditions there is a unique ancestor of
S
, determining whether or not it is reversible. Below are the possible cases for our rules.

All rules move the head in one direction

WLOG, suppose all rules are right rules. We then have that the only cells that have changed from the previous state are the
n
cells displaced to the left of the head. We call these cells
S
L
.
​
Out[]=
If there exists two rules with different inputs
I
1
,
I
2
which have the same output
S
L
, we can’t have reversibility. Replacing
S
L
with
I
1
or
I
2
are both possible previous states.
Out[]=
If all rules have unique outputs, then for any
S
L
, we know that there is a unique rule that output
S
L
and is the only one possible previous state. This means the rules are reversible. Hence, for the case where all rules move in one direction, a set of rules is reducible if and only if all rules have unique outputs.

The rules move the head in both directions

Now, we have two types of rules, the L rules and the R rules. This means, when considering previous possible states of
S
, we could have either come from the left or right cell by the application of a right or left rule respectively. Let
S
1
be a potential previous state for a R-rule, and
S
2
be a potential previous state for a L-rule. This is where the notion of a blocker becomes important, because they represent the position of cells that both a left rule and right rule could have output in. To examine reversibility, we will have to consider the
n+2
cells with the head in the centre.
Out[]=
Suppose that a L-rule and a R-rule both share a common blocker
B
, that the non-blocker cells of the R-rule are called
R
L
, and the non-blocker cells for the L-rule are called
L
R
. We can then form a possible state by concatenating all these. This state appeals to the output of both the R-rule and the L-rule. It therefor means the set of rules is not reversible as we have a irreversible state.
Out[]=
Suppose that no L-rules and R-rules share a common blocker. Then for all states, we can identify the blocker, and determine whether it belongs to a L-rule or a R-rule. Then WLOG, the state can only be output by R rules. In the case that all of the R-rules for this blocker has a unique output, we have reversibility for the same reason as the MA moving in one direction. If all R-rules aren’t unique then we cant have reversibility.
Hence, we have proved that a set of rules are reversible if and only L-rules and R-rules share no common blocker.

Investigating reversible automata

Generating reversible mobile automata for any n, k

The conditions required for the AS theorem allow to enumerate all the reversible rules for any n cell, k colour MA. This was implemented in the MakeReversibleMobileAutomata function, which takes in a 4 inputs. A block permutation number, out permutation number, an odd number of cell n and a number for the amount of colours. It performs steps of categorizing blockers, and matching them to inputs.

Exploration of reversible mobile automata

Lets have a look at our first reversible generated mobile automata! Here are the 4 we will consider.
Here’s some plots with the position of the head on the left hand side
By looking at the above, and through many previous example. It seems many of these have a very repetitive behavior, however there seems to be some that operate slightly more peculiarly.
Before the discovery of the algorithm, I was brute forcing the rules of n=3, k=2 MA, and found one of my favorites! It is rule 12221474 with the ordering system mentioned later in the post. This is reversible, and furthermore appears to have unpredictable behavior. This is something that could be explored.

Cycles in Circular MA

When working with MA, we can restrict the head from leaving the tape by allowing it to cycle around the tape. This means there is going to be a finite number of states that we can have. The diagram above shows us permuting all possible states, and applying out set of rules. We see only closed cycles for the transitions between states. This must be the case for a reversible mobile automata, as if a state were to have two transitions to it, we would not know how to reverse this.
Varying the blockPermutationNum, and outPermutationNum we are able to visualise many causal graphs of reversible mobile automata. This is for n=5, k=2.
​
Below is only the largest cycle of a reversible MA with the corresponding states as
nodes.
Here we look at the distribution of cycle length for our reversible automata automata
We brute force n=3, k=2 for the distribution of the maximum cycle length. We see many rules have a maximum cycle length of 3, and very few have maximum cycle lengths of 5.

Initial exploration

What does it mean for a mobile automata to be reversible?

In classical mechanics, the equations of motion (e.g., Newton’s laws) are time-reversible. This means that if you reverse the velocities of all particles in a system, the system would retrace its path back to its initial state. However, the second law of thermodynamics states that natural processes are irreversible due to increasing entropy and these processes are not time-reversible.
And so for mobile automata, we apply the same intuition. Our laws are going to be our rule set, and our particles are going to be our cells. For a MA to be reversible we require that given any state of our system, we are able to find a unique ‘ancestor’ to that state. If there are multiple ancestors, then we cannot say from which previous state we came from.
For example say we are given the state below, and a set of rules that contain the two rules to the right of the state. Note that
We would say this set of rules is not reversible, because we could Have the two possible previous states given below. The cells are in a similar colouring, except the head is in a different location and therefor there is no unique ancestor.
So some questions we may have could be :
◼
  • How many reversible rules are there?
    • ◼
  • Do they share common traits?
    • ◼
  • How could be check for reversibility?

    • The initial n=3 to 1, k=2 Mobile Automata

    To approach this problem, the initial thought was the question: If I’m given a state, where could it have come from? For this situation, its simple, the current situation of the head must have come from an application of a right rule or a left rule. Using this information, we only have to consider a small radius around the current position of the head. In the diagram below, the lower state is the one which we are trying to reverse. Let us first consider a hypothetical possible right rule.
    ◼
  • The blue arrows preserve color for the application of the rule
    • ◼
  • The black arrow represents a change of color
    • ◼
  • The red arrow shows it is a right rule and the head moves right
    • For the right rule to be applied successfully, we then must have that our state must match the output of the rule in the affected position. Our state must also satisfy that the positions which haven’t been changed are consistent with the inputs of the rule.
    For any state, we can then determine all the rules, and hence previous states, that satisfy these conditions. Here is an example for values sn=10 dn=12. It then also shows these set of rules are not reversible, because there exists a state in which there are more than one ancestor state.
    Above is the state we would like to reverse, and below is the possible rules we could apply to a ancestor state.
    And so, considering every possible 5 cell state, we can brute force the rule space we are working in, for all sn and dn.
    The result is the plot below, where white regions suggest that there exists a state with a large number of ancestors . Looks pretty cool! If you look closely, there are some black regions on the right hand side, these regions are the rules in which all states have 1 ancestor. Selecting these, we see that they are the {sn,dn} pairs:
    With dn being either 256 or 255, otherwise saying that they are only rules containing only left or right rules!
    I suspect that the pattern that arises in the above pattern can be explained using the ordering we have chosen for the rules.

    The n=3 to 3, k=2 Mobile Automata

    ◼
  • sn, dn for the colouring and direction of output cells
    • For these rules, we can apply a similar logic to before to find the possible rules that lead to any given state. Their output must match the state we are trying to reverse, in the correct position for left and right rules respectively. This is an example for a 3 to 3 MA. The bottom state is the state in which we would like to reverse. Above it is the states that could lead up to that state, and the rule which would be applied. For this example some of the states have many previous states, and others have none, which means they’re not achievable by the system unless its a initial state.
    Let us look at an example from our reversible automata! We see that for this one it is one to one.
    For this MA, we see that all relevant permutation only have one possible previous state.

    Code

    Concluding Remarks

    Now that the world of reversible mobile automata has been unlocked there is still much to explore. There is the two dimensional case to consider, and the head could be allow to move more directions that just left and right!

    Acknowledgments

    Credit goes to Sotiris Michos for the proof and a huge huge thank you to my mentor Alejandra Ortis who help write some of the code and showed me some new mathematics. Without these wonderful people, and all the wider summer school this project wouldn’t have been as enjoyable.
    ​
    Thank you to Stephen Wolfram for suggesting this project, and putting me on this unexpected journey.

    References

    1
    .
    S Graham 2023, “[WSS23] Turing machines on graphs” Wolfram Community https://community.wolfram.com/groups/-/m/t/2959123.
    2
    .
    S Wolfram “Active cell motion [in mobile automata]” New Kind of Science https://www.wolframscience.com/nks/notes-3-3--active-cell-motion-in-mobile-automata/

    Cite This Notebook

    Reversibility in mobile automata​
    by Adam French​
    ​https://community.wolfram.com/groups/-/m/t/3210947