[26 form terms for elementary automata] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


26 form terms for elementary automata

(Click here to view the original thread with full colors/images)


Posted by: Michael Schreiber

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.


Posted by: Jason Cawley

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.




Forum Sponsored by Wolfram Research

© 2004-2009 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings