Registered: Sep 2003
Posts: 17

In case you want to look at a way to derive the elementary automata from 26 form terms here is the most recent draft for the Journal of Complex Systems.

Michael F. Schreiber

(Abstract)

An indirect proof of universality is given for the Spencer-Brown form. A term of forms and the universal elementary cellular automaton defined by Wolfram rule number 110 are shown to return the same results for all possible inputs. Spencer-Browns interpretation of the form algebra for numbers is modified. All elementary cellular automaton rules are derived from 26 form terms. Notation and implementation are simplified.

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Very nice.

This may be specialized enough that not everyone sees it importance. But there is something going on here that lies at the basis of Wolfram's intuition that the principle of computational equivalence will prove true.

The simpler we drive the limit of proven universality in formal systems, the easier it gets to prove other simple formal systems, if capable of any serious complexity, are also universal. Michael only had to show the Spencer-Brown form could emulate rule 110. He didn't have to directly show it could emulate any Turing machine, for example.

So it is something of a ratchet. The next guy only has to show something can emulate the Spencer-Brown form, if that happens to be easier to impliment for the system he is looking at. Or any elementary CA. Or... The list will grow.

You can call it heroic induction to see the principle of computational equivalence as established by a handful of examples. But there is a certain logic behind that induction. It gets easier as we go.

Report this post to a moderator | IP: Logged