mverardo / catemplates Goto Github PK

A Mathematica package that enables CellularAutomata researchers (and enthusiasts) to use the Template framework.

License: MIT License

Mathematica 99.75% Shell 0.25%

mathematica cellular-automata wolframlanguage

catemplates's Introduction

CATemplates

CATemplates is a Mathematica package that enables the use of Cellular Automaton (CA) templates, as first described in Representing Families of Cellular Automata Rules.

A Cellular Automaton template allows one to represent potentially huge CA sets through a lightweight data structure, and defer their enumeration to a moment when the rules are really needed.

The CATemplates package provides ways to create user-defined raw templates, along with built-in generator functions able to create templates for rule sets that share a given static property. It also includes operations capable of manipulating templates and enumerating the sets they represent.

Usage

(* Import the CATemplates package after installation *)
In[0] = <<CATemplates`;

(* Generate a template for all elementary colorblind CAs *)
In[1] = tColorblind = ColorBlindTemplate[2, 1.0];

(* Expand tColorblind to get all 16 rule tables of the colorblind elementary CAs (in k-ary form)*)
In[2] = ExpandTemplate[tColorblind]
Out[2] = {{1,1,1,1,0,0,0,0},{0,1,1,1,0,0,0,1},{1,0,1,1,0,0,1,0},{0,0,1,1,0,0,1,1},{1,1,0,1,0,1,0,0},{0,1,0,1,0,1,0,1},{1,0,0,1,0,1,1,0},{0,0,0,1,0,1,1,1},{1,1,1,0,1,0,0,0},{0,1,1,0,1,0,0,1},{1,0,1,0,1,0,1,0},{0,0,1,0,1,0,1,1},{1,1,0,0,1,1,0,0},{0,1,0,0,1,1,0,1},{1,0,0,0,1,1,1,0},{0,0,0,0,1,1,1,1}}

(* Generate a template for all elementary totalistic rules *)
In[3] = tTotalistic = TotalisticTemplate[2, 1.0];

(* Expand tTotalistic to get all of the 16 totalistic elementary CAs*)
In[4] = ExpandTemplate[tTotalistic]
Out[4] = {{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,1},{0,0,0,1,0,1,1,0},{0,0,0,1,0,1,1,1},{0,1,1,0,1,0,0,0},{0,1,1,0,1,0,0,1},{0,1,1,1,1,1,1,0},{0,1,1,1,1,1,1,1},{1,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,1},{1,0,0,1,0,1,1,0},{1,0,0,1,0,1,1,1},{1,1,1,0,1,0,0,0},{1,1,1,0,1,0,0,1},{1,1,1,1,1,1,1,0},{1,1,1,1,1,1,1,1}}

(* Intersect both templates *)
In[5] = tTotalisticAndColorblind = TemplateIntersection[tColorblind, tTotalistic];

(* Expanding the intersection template renders only the elementary rules which are both totalistic and colorblind *)
In[6] = ExpandTemplate[tTotalisticAndColorblind]
Out[6] = {{1,1,1,0,1,0,0,0},{0,1,1,0,1,0,0,1},{1,0,0,1,0,1,1,0},{0,0,0,1,0,1,1,1}}

(* Here is where things get fun!
   We can generate templates for bigger (potentially huge) spaces.
   Let's try to increase r a little: *)
In[7] = $RecursionLimit = Infinity; tr5 = With[{k=2, r=5.0}, TemplateIntersection[ColorBlindTemplate[k, r], TotalisticTemplate[k, r]]];

(* Note we just found templates representatives of all binary radius 5.0 colorblind rules,
   did the same for totalistic rules and intersected the sets.
   All of this executed in 4.52314 seconds on my notebook. 
   Remember there are 2^2^11 = 3.23 10^616 binary, radius 5.0 CAs. 
   Given the new template, all we have to do is a new Expansion to find out how many rules are both totalistic and coloblind in this huge space. *)
In[8] = Length[ExpandTemplate[tr5]]
Out[8]= 64 (* Only 64 of the 2^2048 rules are both colorblind and totalistic. *)

Installation

Open Mathematica, and evaluate the following code:

$UserBaseDirectory

On a terminal, cd to $UserBaseDirectory/Applications, and clone this repository:

git clone [email protected]:mverardo/CATemplates.git

Restart Mathematica, and run:

<< CATemplates`

The package should be loaded.

If you don't want to clone the repository directly inside $UserBaseDirectory, you can clone it to another place and add a SymLink to $UserBaseDirectory/Applications.

#Running unit tests

Run the script:

$ ./test

It checks for every .m file in the "/Tests" directory, and runs it as a mathematica script.

catemplates's People

Contributors

Stargazers

Watchers

Forkers

zorandir csrjr

catemplates's Issues

Create a version of ExpandTemplate that applies the mod function instead of filtering an invalid expansion.

Automatically decide if a modular template intersection is needed

Create a version of ComplementaryTemplates that works with arbitrary values of k.

In pull request #12, @zorandir provided the ComplementaryTemplates function, that enables the generation of complementary templates in the binary case.

This would be a generalization so that this function works with any value for k.

Refactor ComplementaryTemplates to use internal constants or private functions

Currently, the function is defined in a way that is hard to read. It would be better if it used private functions or constans to increase it's readability.

Modify names of the post-expansion functions

New names should be:
ModKMapper,
IdentityMapper,
FilterVariableAssignments, and
FilterKOutOfRange.

Bug when handling asymmetric radii

Below, two cases to make the bug evident, both for k=3. Possibly, the bug occurs only for k>2, but this should be checked.

In[6]:= Intersection[
ExpandTemplate[With[{k = 3, r = 0.5}, ColorBlindTemplate[k, r]]],
ExpandTemplate[With[{k = 3, r = 0.5}, TotalisticTemplate[k, r]]]]

Out[6]= {{2, 0, 1, 0, 1, 2, 1, 2, 0}}

ExpandTemplate[
With[{k = 3, r = 0.5},
TemplateIntersection[
ColorBlindTemplate[k, r],
TotalisticTemplate[k, r]]]] // Length

Out[5]= 0

In[10]:= Intersection[
ExpandTemplate[With[{k = 3, r = 1.5}, ColorBlindTemplate[k, r]]],
ExpandTemplate[With[{k = 3, r = 1.5}, TotalisticTemplate[k, r]]]]

Out[10]= {{2, 1, 0, 1, 0, 2, 0, 2, 1, 1, 0, 2, 0, 2, 1, 2, 1, 0, 0, 2,
1, 2, 1, 0, 1, 0, 2, 1, 0, 2, 0, 2, 1, 2, 1, 0, 0, 2, 1, 2, 1, 0,
1, 0, 2, 2, 1, 0, 1, 0, 2, 0, 2, 1, 0, 2, 1, 2, 1, 0, 1, 0, 2, 2, 1,
0, 1, 0, 2, 0, 2, 1, 1, 0, 2, 0, 2, 1, 2, 1, 0}}

In[11]:= ExpandTemplate[
With[{k = 3, r = 1.5},
TemplateIntersection[ColorBlindTemplate[k, r],
TotalisticTemplate[k, r]]]] // Length

Out[11]= 0

Create a ExceptionTemplates operation

Create a operation that generates the replacements in a template that generate invalid rules.

RuleTemplateVars returns the symbols in lex order

To reproduce:

In > RuleTemplateVars[BaseTemplate[2, 2]]����
Out> {x0, x1, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x2, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x3, x30, x31, x4, x5, x6, x7, x8, x9}�����

Change ColorBlindTemplate generator to use modular templates

How should a template resultant from an intersection expand itself?

Implement a template ADT

Should look like this:

Template
{
template : {x8,x7,x6}
ExpansionFunction : Partial[ExpandTemplate[k,r]]
k : 2
r : 1
N : 3
}

Refactor ElementaryTemplates to use internal constants or private functions

Currently, the function is defined in a way that is hard to read.
It would be better if it used private functions or constans to increase it's readability.

Translate commentaries to english

ModularTemplateIntersection produces templates that don't preserve the index-variable duality

In >> ModularTemplateIntersection[TotalisticTemplate[], OuterTotalisticTemplate[], 2]
Out >> {x7, x5, x5, x2, x5, x2, x2, x0}

There should be the possibility of an iterative way for expanding templates that demand a lot of memory

Here's an example, with 32 variables in the template (Mathematica crashes in my machine with 16GB):
ExpandTemplate[With[{k = 2, r = 2.5}, ColorBlindTemplate[k, r]]]

In a case like this, the user should be warned and given the possibility of an iterative expansion, that would yield the results little by little on the Mathematica notebook, or directly into file.

Implement imprisonment expressions with the new template ADT

Adapt template intersection to the new ADT

Create an expansion function for templates generated with a mod N different from k.

IN >> ExpandTemplateModK[ModNStateConservingTemplate[3], 3]

Results in invalid rules, as ModNStateConservingTemplate is generating a Mod 3 template with k=2.

There should be an expansion function that performs a mod N in the end, and removes invalid rule tables, as does the default ExpandTemplate.

Create a template generator for parity conserving CAs

Create a version of TemplateIntersection that works with templates generated with Mod[].

this version of the TemplateIntersection function should use the modulus -> k option, and translate the C[i] constants into template variables.

Currently, the problem with this approach is that the C[i] constants can't be called x_i, as this would create a semantic conflict between these variables and the ones from templates generated without mod.

It's still not clear if all new intersections should be named with different variables, or if the C[i] should get a new name with a new template (possibly resulting from intersections).

Remove SymmetricTemplate function, add generalized MaximumSymmetryFunction

$RecursionLimit set to Infinity should be default in the package.

The example in the READ.ME,

With[{k = 2, r = 5.0},
TemplateIntersection[ColorBlindTemplate[k, r], TotalisticTemplate[k, r]]];

doesn't work, unless $RecursionLimit set to a big value. As a matter of uniformity, maybe it should be set to Infinity as default. By the way, until this is done, READ.ME should be altered with an example that would work.

Given a template, create an operation that generates a set of templates that represent the complementary rules of the original template.

Given a template, it is expected that this operation create a set of templates that if expanded generates all rules that the original template don't represent

Create doc pages

We desperately need documentation on this project!

Fix ColorBlindTemplate (broken with TemplateIntersection's refactoring)

To reproduce:

ColorBlindTemplate[3]

RestrictedTemplateIntersection[t1,t1] results in {} instead of t1

In := t1 = BuildTemplate[3, 1.0, {2, x1 \[Element] {0, 2}, 0}, RestrictedExpansion];
In := t2 = BuildTemplate[3, 1.0, {2, x1, 0}, RestrictedExpansion];
In := TemplateIntersection[t1, t2] 
Out = <|"k" -> 3, "r" -> 1., "rawList" -> {}, "expansionFunction" -> RestrictedExpansion|>

Out should be

<|"k" -> 3, "r" -> 1., "rawList" -> {2, x1 \[Element] {0, 2}, 0}, "expansionFunction" -> RestrictedExpansion|>

Generalize SymmetricTemplate to work with any values of k.

Currently, it works only with binary templates.

ModularTemplateIntersection produces wrong results on equivalent templates

The following templates are equivalent when expanded mod 3:

In >> t1 = {2 + x1, x0};
In >> t2 = {x1, x0};

Problem is that their intersection is empty:

In >> ModularTemplateIntersection[t1, t2, 3]
Out >> {}

Changing one of the template's variables to yi corrects this problem, tough:

In >> ty2 = Symbol[StringReplace[SymbolName[#], "x" -> "y"]] & /@ t2;

In >> ModularTemplateIntersection[t1, ty2, 3]
Out >> {2 + x1, x0}

Maybe ModularTemplateIntersection should translate one of it's arguments to ys?

Adapt current generator functions to return template ADTs

Break the UnitTests.nb into smaller script files to eliminate conflicts

Maybe there is a way to use this kind of script to run sequential tests and generate a report in the end.

Or, perhaps, use something like this to run separate tests defined in a text file.

Move ExceptionTemplates function from Basic.wl

So, @zorandir , where do you think it should be moved to?

ColorBlindTemplate[4] produces error.

Probably because it uses ImprisonmentExpressions internally for k>4, and ModularTemplateIntersection is not prepared to treat these kinds of expressions.

Validate a template's k and r before intersection

When mixing modular and non-modular templates, ModularTemplateIntersection depends on the order of it's arguments

Given the templates:
t1 = ColorBlindTemplate[3, 2];
t2 = TotalisticTemplate[3, 2];

If ModularTemplateIntersection is used as follows:
In >> ModularTemplateIntersection[t2, t1, 3]

Out >> {2, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0}

The output is a valid k-ary rule table.
If the order of the arguments are reversed, the output is:

{2, 0, -2, 0, 1, 2, -2, 2, 0, 0, 1, 2, 1, 2, 0, 2, 0, 1, -2, 2, 0, 2, 0, -2, 0, -2, 2, 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1, 2, 0, -2, 2, 0, 2, 0, -2, 0, -2, 2, 2, 0, -2, 0, -2, 2, -2, 2, 0, 0, -2, 2, -2, 2, 0, 2, 0, -2, -3, 1, -1, 1, -1, -3, -1, -3, 1, 1, -1, -3, -1, -3, 1, -3, 1, -1, -1, -3, 1, -3, 1, -1, 1, -1, -3, 1, -1, -3, -1, -3, 1, -3, 1, -1, -1, -3, 1, -3, 1, 5, 1, 5, 3, 3, 1, 5, 1, 5, 3, 5, 3, 1, 5, 3, 1, 3, 1, 5, 1, 5, 3, 3, 1, 5, 1, 5, 3, 5, 3, 1, 1, 5, 3, 5, 3, 1, 3, 1, 5, 4, 2, 0, 2, 0, 4, 0, 4, 2, 2, 0, 4, 0, 4, 2, 4, 2, 0, 0, 4, 2, 4, 2, 0, 2, 0, 4, 2, 0, 1, 0, 1, 2, 1, 2, 0, 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 0, 4, 2, 4, 2, 0, 2, 0, 4, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 4, 0, 1, 2, 4, 2, 0}

Wich, clearly, is not a valid rule table.