Bijective cellular systems
Introduction"Bijective cellular systems" is an umbrella term, intended to describe reversible cellular systems where global reversibility is attained by repeated use of a small, finite bijections which are applied locally.
Previously I identified that partitioning was a subset of a larger number of techniques for devloping reversible systems. I described a larger set that included partitioning that I called isometric.
Now it appears that isometric cellular systems are themselves a subset of a larger set - the set of bijective cellular systems. Isometric systems are not the only way to manufacture reversible cellular systems using small bijective maps.
The rest of this page is devoted to another method of producing reversible cellular systems using bijections - one which appears not to have been previously described or clearly identified. I call this technique "fencing".
It will be considered initially as an extension of partitioning. However it applies to all isometric systems.
It appears that two of the restrictions employed during partitioning can usefully be relaxed under certain conditions.
These restrictions are:
The idea is a somewhat complex and difficult to explain - I'll do the best I can.
I assume knowledge of partitioning - if you are in need of such knowledge, I recommend you start here.
DiagramsIn the following diagrams, colours have the following significance:
These diagrams roughly outline the system I was thinking of when I came up with the idea.
Here is a (somewhat abstract) diagram of a conventional partitioning scheme:
I'll assume for the moment that regions not within the co-domains of partitions are preserved unchanged from generation to generation during evolution of the system.
First note that, the co-domain can be contracted - so that it forms a subset of the domain. One can imagine elements in the domain in the region covered by the co-domain to form a bijection with the latter - while elements outside the co-domain always remain unchanged. This can be done without any significant change to the reversibility of the resulting system.
Then note that it is no longer necessary for the domains to be disjoint - since they are effectively fixed - and consequently they may be allowed to overlap in the region that is effectively fixed:
Precise formulationThe idea can be more precisely formulated in such a way that it applies to all isometric schemes - not just as an extension of partitioning. Also the requitement that certain regions remain unchanged is not necessary - and can be eliminated.
The following critera are presented in the form of a recipe:
Discussion of these criteria follows.
NotesIt appears to be a theorem that any systems created using this technique will be equivalent to some isometric system using finer granulations of time - i.e. a sysyem with N times as many time steps producing the same temporal evolution.
Seen in this light the technique appears to be a speed-up - a way of evaluating several iterations of an isomentric system concurrently under some circumstances.
ExamplesAs a simple example, one implication is that - in a partitioning cellular system - the domain of the partition transition function may be expanded to include whole entire neighbouring partitions (provided that there remains a bijection between the original domain and co-domain) while maintaining reversibility.
I imagine it will find application when people want to share information near the edges of partitions by making the partitions slightly overlap.
As a concrete example, the technique arose from the desire to create a reversible cellular system which seemed to demand its usage. You can see that system in action here - and it comes with diagrams of the neighbourhood it uses.
SummaryI have presented a new technique for creating reversible cellular systems. It was inspired by the existing techniques for making isometric cellular systems.
I hope others will find the technique useful.