Computational Equivalence: Spencer-Brown Form 110

Michael Schreiber

Proof: A Spencer-Brown form term is equivalent to Wolfram rule 110. This term is a nested form and accepts three inputs. Bit inputs are translated into form versus empty. Computation returns one form output for three form inputs. Decoding returns one for form and zero for empty. All eight possible inputs return like rule 110.

Consequence: A distinction process like form is all you need to compute. A system is equivalent to rule 110 if it can distinguish: more than one is one, but one inside one is none. This is equivalent to DiscreteDelta in Mathematica.

Observations: According to Spencer-Brown a form may recycle output as input. It turns out that this can be used to carry out the addition of bit streams. Neither conventions for translating between form and bit nor conventions about input order are necessary. Such conventions can be accommodated by compositions of transformations. One transformation permutes inputs. The two others switch translations of inputs and outputs. There are 26 characteristic forms. All 256 rule numbers are derived by compositions of the three transforms. Their characteristic letters articulate a palindrome.
  

Created by Mathematica  (April 20, 2004)