Invertible Wolfram automataPrevious reversible 1D automataA method of generating reversible automata from certain "quasi-linear" 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 non-uniform configurations.
Uniform reversible rulesThere are a number of "trivial" uniform reversible Wolfram automata. Thes include the "STAY-THE-SAME" (rule 204), and "INVERT"
(rule 51), rules. If periodic boundary conditions are used,
"SHIFT-LEFT" (rule 193), and "SHIFT-RIGHT" (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.
Non-uniform reversible rulesIf non-uniform 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 non-uniform 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 near-uniform 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 right-hand 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 left-hand 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 right-hand 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 end-to-end, 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 left-hand ends, and rules 85, 102, 170 and 153 should be used on the right-hand 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 non-trival types of reversible Wolfram automata operating on finite fields, which employ non-linear 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 automata-based pseudorandom number generators for built-in self test, IEEE Transactions on Computer-Aided Design, August 1989, volume 8, number 8, pages 842-859.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 1466-1473.
|
