wolframscience.com

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > News & Announcements > 26 form terms for elementary automata
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
Michael Schreiber
Wolfram Research
Vienna, Austria, Europe

Registered: Sep 2003
Posts: 17

26 form terms for elementary automata

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

Old Post 09-30-2003 04:00 AM
Michael Schreiber is offline Click Here to See the Profile for Michael Schreiber Click here to Send Michael Schreiber a Private Message Visit Michael Schreiber's homepage! Edit/Delete Message Reply w/Quote
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

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

Old Post 10-03-2003 05:31 AM
Jason Cawley is offline Click Here to See the Profile for Jason Cawley Click here to Send Jason Cawley a Private Message Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


 

wolframscience.com  |  wolfram atlas  |  NKS online  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-14 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives