Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bitbanging 1D Reversible Automata

richiejp.com

Post reply on HN
Print view View original

11–20 of 24 posts

Re: Bitbanging 1D Reversible Automata

#11

Post by hairtuq »

The author wonders:

> In theory at least, the compiler can see that rule only has 256 values and create a reduced version of ca1d_rule_apply for each value. Whether it actually does is not of much practical concern when the rendering code is the bottle neck. However it’s interesting to see if the compiler can deduce the best solution or whether anything trips it up.

The compiler is unlikely to get the optimal result here. The core of this is finding the best instruction sequence for a ternary boolean operation encoded in 8 bits; it's the same job needed for emulating the AVX512F "vpternlog" instruction. This can always be done in at most 5 instructions (or 4 if you have andnot/ornot/xornot), but it's not straightforward to do this. Here is some code that calculates optimal instruction sequences (by letting z3 do the heavy lifting): https://github.com/falk-hueffner/ternary-logic-optimization

Re: Bitbanging 1D Reversible Automata

#12

Post by danwills »

tugu77 wrote: post #7

Automaton. The singular is automaton. Automata is plural.

I've sometimes thought it might be reasonable to think of a single cell in the system as an 'automaton' which might make it somewhat ok to call the whole collection of cells 'automata'.

I accept that there's two levels here though and sometimes people refer to the system as a whole as being a single automaton even if there's loads of cells.

Re: Bitbanging 1D Reversible Automata

#14

Post by genewitch »

genewitch wrote: post #9
richiejp wrote: post #6

Earlier quoted context omitted.

could you provide a link to the code?

i wrote something similar a real long time ago, but it was a pig, super slow. So i upgraded to winpro or whatever and had copilot figure out what was slowing it down, and it was a simple fix, and i fleshed out the UI a bit. I forget where i first saw the rules, but when i went and fixed it up i used the wolframalpha reference[0] Adjust the screen rez. i am not a software developer and i put stuff on github as additio…

oops you need to "cd cellular" after the venv command! I proofread that 4 times and still missed the cd, and i had just set it up for my kid to play with (he asked!)

Re: Bitbanging 1D Reversible Automata

#15

Post by richiejp »

QuadmasterXLII wrote: post #10
tugu77 wrote: post #7

Automaton. The singular is automaton. Automata is plural.

The post describes multiple automata though?

Yes it does. Even discarding arguments that different rules in the same class are the same automaton and multiple cells are the same automaton, the article includes reversible and non-reversible automata which are distinct classes.

Re: Bitbanging 1D Reversible Automata

#16

Post by tromp »

The author make automata reversible by xoring with the previous row's cell. But some rules are reversible without this trick. For example rule 0xf0:

    111 110 101 100 011 010 001 000
     1   1   1   1   0   0   0   0
will shift all cells one step to the right and is thus the reverse of rule 0xaa which shifts all cells to the left:

    111 110 101 100 011 010 001 000
     1   0   1   0   1   0   1   0
My question is how can we test which of the 256 rules are reversible and how do they pair up?

Re: Bitbanging 1D Reversible Automata

#18

Post by Y_Y »

tromp wrote: post #16

The author make automata reversible by xoring with the previous row's cell. But some rules are reversible without this trick. For example rule 0xf0: 111 110 101 100 011 010 001 000 1 1 1 1 0 0 0 0 will shift all cells one step to the right and is thus the reverse of rule 0xaa which shifts all cells to the left: 111 110 101 100 011 010 001 000 1 0 1 0 1 0 1 0 My question is how can we test which of the 256 rules are r…

> My question is how can we test which of the 256 rules are reversible and how do they pair up?

I wondered this too. It feel like a generalization of the well-studied deconvolution problem, but thankfully without noise.

I haven't had my coffee yet, but some quick googling any thinking didn't deliver an answer, so I'd just try enumerating all the rules and seeing which ones invert each other.

Or, take all permutations of five bits, and find the central three bits in the next generation. If-and-only-if all patterns resulting in the three bits have the same central bit in the original pattern, then the rule is invertible.

Re: Bitbanging 1D Reversible Automata

#19

Post by tromp »

Y_Y wrote: post #18
tromp wrote: post #16

The author make automata reversible by xoring with the previous row's cell. But some rules are reversible without this trick. For example rule 0xf0: 111 110 101 100 011 010 001 000 1 1 1 1 0 0 0 0 will shift all cells one step to the right and is thus the reverse of rule 0xaa which shifts all cells to the left: 111 110 101 100 011 010 001 000 1 0 1 0 1 0 1 0 My question is how can we test which of the 256 rules are r…

> My question is how can we test which of the 256 rules are reversible and how do they pair up? I wondered this too. It feel like a generalization of the well-studied deconvolution problem, but thankfully without noise. I haven't had my coffee yet, but some quick googling any thinking didn't deliver an answer, so I'd just try enumerating all the rules and seeing which ones invert each other. Or, take all permutations…

For a rule to be reversible, it should have a 1 in 4 places, ie. hamming weight 4. I suspect all (8 choose 4) = 70 rules might be reversible.
Post reply on HN