Reversible Cellular Automata Part 1
Posted: Sun Feb 26, 2023 3:21 pm
Cellular Automata are exciting and have been discovered in the 60's
Each CA rule begins from a well ordered state and some evolve into a chaotic one.
Initial conditions are important.
They are deterministic they apply a simply rule to determine the value of each cell
using the values of neighbouring cells at time t-1
E.g Rule 214
111 110 101 100 011 010 001 000
1-----1-----0-----1-----0-----1-----1-----0
Left=1 Center=0 Right=1 ==> Cell=0
They are identified by the value of the each rules binary number e.g 11010110 = 214
I have written a short function that takes any rule and generates its boolean form
So now you can generate any rule
Now we need to add a 4th value that being the cells value 2 time steps back at t-2
Using this and incorporating it into the rule of any CA will make it fully reversable:
top being the value of the cell at t-2
Here is the output of a program that applies a reverse rule 214 to recover a random seed:
Now lets apply the rule using the seed:
Ok now we want to recover the seed so we shall apply the same rule in reverse to do this I will
generate a mask - when applied to the output it will reveal the seed. The mask is made from the reverse application of the rule on the above output:
Now we simply apply the mask to recover the hidden seed using the mask!!
As you can see by using the reverse rule you can exactly recover the seed after applying the rule and then reversing the rule.
When you apply the rule to the seed use the following:
This will seed the rule 214 and make it reversable
To reverse the rule and recover the seed use this:
(NB. ^ = XOR)
This might be a useful way to encrypt your data so long as the rule
remains secret!
Each CA rule begins from a well ordered state and some evolve into a chaotic one.
Initial conditions are important.
They are deterministic they apply a simply rule to determine the value of each cell
using the values of neighbouring cells at time t-1
E.g Rule 214
111 110 101 100 011 010 001 000
1-----1-----0-----1-----0-----1-----1-----0
Left=1 Center=0 Right=1 ==> Cell=0
They are identified by the value of the each rules binary number e.g 11010110 = 214
I have written a short function that takes any rule and generates its boolean form
- Code: Select all
int rule_gen(int rule,int left,int center,int right,int top){ //Generate rules from rule code
int out;
if(bitset<8>(rule)[0]==1){
if(left==1 & center==1 & right==1){out=1;}
}else{
if(left==1 & center==1 & right==1){out=0;}
}
if(bitset<8>(rule)[1]==1){
if(left==1 & center==1 & right==0){out=1;}
}else{
if(left==1 & center==1 & right==0){out=0;}
}
if(bitset<8>(rule)[2]==1){
if(left==1 & center==0 & right==1){out=1;}
}else{
if(left==1 & center==0 & right==1){out=0;}
}
if(bitset<8>(rule)[3]==1){
if(left==1 & center==0 & right==0){out=1;}
}else{
if(left==1 & center==0 & right==0){out=0;}
}
if(bitset<8>(rule)[4]==1){
if(left==0 & center==1 & right==1){out=1;}
}else{
if(left==0 & center==1 & right==1){out=0;}
}
if(bitset<8>(rule)[5]==1){
if(left==0 & center==1 & right==0){out=1;}
}else{
if(left==0 & center==1 & right==0){out=0;}
}
if(bitset<8>(rule)[6]==1){
if(left==0 & center==0 & right==1){out=1;}
}else{
if(left==0 & center==0 & right==1){out=0;}
}
if(bitset<8>(rule)[7]==1){
if(left==0 & center==0 & right==0){out=1;}
}else{
if(left==0 & center==0 & right==0){out=0;}
}
return out;
}
So now you can generate any rule
Now we need to add a 4th value that being the cells value 2 time steps back at t-2
Using this and incorporating it into the rule of any CA will make it fully reversable:
- Code: Select all
out = (out==1 ^ top==1)? 0:1;
top being the value of the cell at t-2
Here is the output of a program that applies a reverse rule 214 to recover a random seed:
- Code: Select all
---Seed Before 214--- ....................0.....................0....... ..00.....................................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........... ..........................00......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.........................
Now lets apply the rule using the seed:
- Code: Select all
---Output from Rule 214--- ........................0......................... ........................0......................... ........0..............0.0....................0... ........00............00000..................000.. ........000..0.0.....0..0.00................0..00. .......00.0000..0...00...0000............0.00..000 00....0..0000.0.00.0..0.....00......0...000..000.0 000..00......00.00.0..00.00.000....000.0..0...0.00 .0000..0.000....0...0000..0.0000..0..0.0...0...0.. .0.00..0..000000.....00.0...0..0000....00..00..0.. 0.00.00.0.0.0000.....0.00000...000.0.0000000000.00 00..0.000..00...0...0.0..000..00..00..0..00..000.0 .0..0000...0..0.00.0000..0..00......00...0...0.000 0.0000....0..00.00...0.00....0.0.00.....0...0.000. 00.0...0.0..0...0.00..0.0.0....0..0000.00..000...0 .00..000.0.00.00.0.00.00..00.00.0.000....00..0.0.. .0000.0.....0..00.000.00.000..0.0.0...00..0....000 .0.000...0..00.000....0.....0.......00.00.00.00000 ..00.0..000000.0.0.0.0...00..00.0.00.0000.00..0... ....0.00..00....0..0.0..0.00..0.0..000....0.0...00 0.0.00.0..0..0..0.0...0000..0....0000..000.00000.0 0.0.000.00..0000..00...0.0..000...0...0.000..00000 0...0.00.0.0..00.00.0...0.000000....00000.0.....0. .000.000...0..0....000..00.0...00.0..0.0.0...00..0 0.000.0.000.00...0...000000..0.00.00..0.00..0.00.0 000.00.0.000.0..0000.0000.0.00.0..000.00..000000.0 .0.0000000.00.00..00.0..00.......00.0.00...0.0...0 0.0...0.0.0000.0..0......0..00.00..0..0.0...0..00. 000.0..0.0...00.00...0..0.00.0..0..0.0.000..0.0.00 .0..00.000.0.000.0..0000.0.00.0..00..00..000..0000 0..000.00..0.0.00.00..00.0000000..0.000..000.000.. 0.0....0..0...0000.0..0.000..0.00......000........ ..0.000..00......00.00.00.....00000.00..0..0.000.0 .0...00.0..0..00.000.00.0.0......00..00...00..00.0 .0...0..0..000.0.0.000000.00..00.0.0.00000..0.0... 0.0.0..0.000000...000..00.0000.0..00.0.000..0....0 000.0.000.0...0........00.0.000.0.....00..00.00.0. 00......00..0..0..000.000..00.000000.......00.0.00 ....0.0.00.000.000.00...00...000.0000.00...000..00 .0.00.0.0....0.00000.00..000....00..0..00.00.0.00. 00.........0...0..0.0.000000000......0.00...0..... ..000.0.0.00000....00000....000000...0.0.00.0..000 ...00.0.0...000......0..000.0..0000.0...0.0..00.00 0..0.....00.0..0...0....000....0..0.0...00.0..000. 000...0...0....00.0000.0...00.0......0.000000.00.0 .00..000...00.000...00.000..0.0...0..0....0.0.0.0. .0.00..00...0....00.0..0.00....0.0000.000..0...00. 0.0.0..000...000..0...0..0000..0...000.000.0.....0 0000.000.00...000..0000..0.0000.00.0.000.0..0..0.. 00.00.0.0000..0.00..00.0..00.000.0..000.0.0.00000.
Ok now we want to recover the seed so we shall apply the same rule in reverse to do this I will
generate a mask - when applied to the output it will reveal the seed. The mask is made from the reverse application of the rule on the above output:
- Code: Select all
---Mask from Seed 214 Reverse--- .................................................. .................................................. 00000000000000000000000.0.000000000000000000000000 0000000...000000000000.....000000000000000000...00 0000000....0000000000.00.0..0000000000000000.00..0 0000000..0....0..000..000....00000000000000..00... .00000.00....0.0..0.00.00000..0000000000..000...0. ...00..000000..0..0.00..0..0...0000...0.00.000.0.. 00...00.0...0000.000....00.0.0..00.00.0.000.000.00 0.0..00.00......00000.00.000.00....00000.00..00.0. .0..0..0.0.0....00000.0.....000...0.0..........0.0 ..00.0...00..000.000.0.00...00..00..00.00..00...0. 0.00....0.0000.0..0....00.00..000000.0000.000.0... .0....0000.00..0..000.0..0000.0.00.00.00.000.0...0 ..0.000.0..0.000.0..00.0.000000.00....0..00...000. 0..00...0.0..0..0.0..0..00..0..0.0....000..00.0.00 0..0.0.00000000......0..0...00...0.0000.00.0000... 0.0...000.000.0...0000.00000.0000000..0..00.0..... 00..0.00......0.0.0...000..0...0.0..0....0..00.000 0000.0..00..0000.00.0.00.0..00.0.00....000.0.000.. .0.0..0.00.00.00.0.000.......0000.0..00...0.....0. .0.0...0..00....00.0000.0.00...000.000.0...00..... 0000.0..0.0.00..0....000.0......0000.....0.00.00.0 0...0....00.00.0000...00..0.000..0..0.0.0.0.0..00. .0...000...0..000.000......00.0..0..00.0..00.0..0. ...0..0.0...0.00....0...00.0..0.00...0..00......0. 0.0.......0..0..00..0.000.0000000..0.0..000.0.000. .0.000.0.0....0.00.00000..00..0..00.00.0.000.00..0 ...0.00.0.000..0..000.0000..0.00.00.0.0...00.0.0.. 0.00..0...0.0...0.00......0..0.00..00..00...00.... .00...0..00.0.0..0..00..........00.0...00...0...00 .0.0000.00.000....0.00.00..00.0..000000...00000000 00.0...00..000000..0..0.000000.....0..00.00.0...0. 0.000..0.00.00..0...0..000.000000..00..000..00..0. 0.000.00.00...0.0.0.....00..00..0.0.0.....00.0.000 .0.0.00.0......000...00.00....0.00..0.0...00.0000. ...0.0...0.000.00000000.00.0...0.00000..00..0..0.0 ..000000..00.00.00...0..000..0......0000000..0.0.. 0000.0.0..0...0...0..0000.000...0....0..000...00.. 0.0..0.0.0000.0.....0..0....0000..00.00..0..0.0..0 ..000000000.000.00.0.0..0......000000.0..000.00000 00...0.0.0.....0000......000......000.0.0..0.00... 000..0.0.000...000000.000..0.00....0.000.0.00..0.. .00.00000..0.00.000.00000..0000.00.0.000..0.00...0 ...000.000.0000..0....0..00..0.000000.0......0..0. 0..00...000..0...000..0.0.00.0.000.00.0000.0.0.0.0 0.0..00..000.0000..0.00....0000.0....0...00.000..0 .0.0.00...000...00.000.0.....00.000...0...0.00000. ....0...0..000...00....0..0....0..0.0...0.00.00.00 ..0..0.0....00.0..00..0..0..0...0.00...0.0.0.....0
Now we simply apply the mask to recover the hidden seed using the mask!!
- Code: Select all
---Mask applied to Output 214 Reverse--- ........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........... ..........................00......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.........................
As you can see by using the reverse rule you can exactly recover the seed after applying the rule and then reversing the rule.
When you apply the rule to the seed use the following:
- Code: Select all
rule = 214
seed==1 ^ top==1 ^ rule==1
This will seed the rule 214 and make it reversable
To reverse the rule and recover the seed use this:
- Code: Select all
NOT (top==1 ^ rule==1)
(NB. ^ = XOR)
This might be a useful way to encrypt your data so long as the rule
remains secret!