News for hackers. Stuff that matters.

A comment on Bitbanging 1D Reversible Automata. Parent comment

Re:Bitbanging 1D Reversible Automata by Y_Y on Friday December 13, 2024 @04:16AM (#42407122)
> 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 and answer, so I'd just try enumerating all the rules and seeing which ones invert each other.

[ Parent | on HN ]
Re:Bitbanging 1D Reversible Automata by tromp on Friday December 13, 2024 @04:52AM (#42407287)
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.
[ Parent | on HN ]
Re:Bitbanging 1D Reversible Automata by orlp on Friday December 13, 2024 @07:47AM (#42408011)
It turns out that only the identity gate and the left <-> right moving rules are reversible, plus their negated variants, see my other comment.
[ Parent | on HN ]