Invertible Wolfram automataPrevious reversible 1D automataA method of generating reversible automata from certain "quasilinear" Wolfram rules was described briefly on the page devoted to the "path" technique  a method of constructing cellular automata with inverses whose neighbourhoods are unboundedly large.Unfortunately, this construction changes the neighbourhood used in such a way that the domain of the neighbourhood is shifted one cell to the right. This is undesirable  in that it prevents information diffusion in one direction through the automata, and means the greatest distance between a point in the domain and a point in the range is increased by up to a third. This page discusses some linear Wolfram rules, which may be used to compose reversible automata if used in nonuniform configurations.
Uniform reversible rulesThere are a number of "trivial" uniform reversible Wolfram automata. Thes include the "STAYTHESAME " (rule 204), and "INVERT "
(rule 51), rules. If periodic boundary conditions are used,
"SHIFTLEFT " (rule 193), and "SHIFTRIGHT " (rule 240)
(and their inverting equivalents, rules 62 and 15) are reversible.In addition, rules 90, 105, 145, and 150 sometimes produce reversible finite automata. Whether they are invertible or not depends on the size of the field, and on the type of boundary conditions used.
Nonuniform reversible rulesIf nonuniform automata may be employed, the number of reversible automata increases:
Two adjacent cells may swap states with one another  provided they completely
ignore their other neighbours.
Rules 90, 105, 145, and 150
It's been known for some time that certain composite automata, constructed from rule 90 and rule 150 are reversible. Determining whether linear cellular automata are invertible can be done by finding whether the matrix corresponding to the transition function is singular (by calculating its determinant). This is described in more detail here. Generating arrays of rules 90 and 150 at random  and testing them for reversibility  reveals that a fixed proportion (approaching exactly 66.66% as the size of the automata increases) of them are reversible. The main result presented here is that it is possible to determine if an arbitrary nonuniform combination of rules 90, 105, 145, and 150 is reversible by performing a few fairly simple calculations. For an automata with n cells the test takes O(n) time to conduct. This fact  in conjunction with the consistently high frequency and nearuniform distribution of reversible automata generated at random from these rules  means that reversible automata of any size may be efficiently generated. The technique was found empirically. It can be used whether periodic boundary conditions or fixed boundary conditions are used. The test involves checking if four states of the automata have precursors. The states checked are 0, 1, 2 and 3  i.e. states "...00000", "...00001", "...00010" and "...00011". If these automata have precursors, the resulting automata is reversible. To determine if an automata has a predecessor, it is not necessary to search through all possible configurations of the automata. Insted the following proceedure may be used: Starting with a "zero" at the righthand end of the possible precursor, this uniquely determines the next cell to the left in the possible precursor. In turn this determines the state of the next cell to the left. When the far lefthand end of the automata is reached, either the predecessor will have been located  or the proceedure will break and the last cell will be determined incorrectly. If a precursor has not been found, then start again with a "one" at the righthand of the possible precursor and repeat the above proceedure. If this also fails, the state has no precursor, and the automata is irreversible. Otherwise a precursor for that state will have been found. After all four states have been checked, reversibility of the entire automata has been determined. As well as determining reversibility, this provides a concrete method of determining the inverse function. Following the proceedure above to determine whether a state has a precursor will always exactly determine it  if it has one. The technique works fairly rapidly  on a serial machine.
Concatenating automataSince fixed boundary conditions may be used, these rules may be laid endtoend, if required, while maintaining reversibility. The rules at the ends of each segment need adjusting to prevent information flow between the sections  i.e. rules 15, 62, 240, and 193 should be used on the lefthand ends, and rules 85, 102, 170 and 153 should be used on the righthand ends.
Periodic boundary conditionsThe construction method will work if fixed boundary conditions are used. If periodic boundary conditions are used, the procedure for determining reversibility is very similar. Typically, about half as many reversible automata exist if periodic boundary conditions are used.If you're using periodic boundary conditions, concatenating them into larger automata is no longer possible.
Other Wolfram rulesThe rules employed here are linear  and consequently of limited use for cryptography, and of no use for systems which require universal computation.Unfortunately, the chances of locating nontrival types of reversible Wolfram automata operating on finite fields, which employ nonlinear rules in avy cells currently appears to me to be rather remote.
Java appletA Java applet employed during the explorations resulting in this method is available [here].[Note that this automata does not implement all sections of the technique described here.]
ReferencesHortensius, P. D., McLeod, R. D., Pries, W., Miller, D. M. and Card, H. C., Cellular automatabased pseudorandom number generators for builtin self test, IEEE Transactions on ComputerAided Design, August 1989, volume 8, number 8, pages 842859.Hortensius, P. D., McLeod, R. D.and Card, H. C., Parallel random number generation for VLSI systems using cellular automata, IEEE Transactions on Computers, 1989 volume 38, number 10, pages 14661473.
