[NKS 2004: Nigel Goldenfeld, Computational Irreducibility and the Predictability...] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


NKS 2004: Nigel Goldenfeld, Computational Irreducibility and the Predictability...

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


Posted by: Catherine Boucher

Nigel Goldenfeld
University of Illinois, Urbana-Champaign
Computational Irreducibility and the Predictability of Physical Systems

Session:
10:30am, April 23, 2004, Eden Vale A
Pure NKS: The Study of Simple Programs
Part 1: General Features of Cellular Automata

Abstract:

Using elementary cellular automata (CA) as an example, I show how to coarse grain CA in all classes of Wolfram’s classification. The resulting coarse-grained CA emulate the large-scale behavior of the original systems without accounting for small-scale details. Computationally irreducible physical processes can be predictable and even computationally reducible at a coarse-grained level of description. At least one of the CA that can be coarse grained is irreducible and known to be a universal Turing machine.

http://www.wolframscience.com/confe...s/index_28.html


Posted by: Mike Lin

Here are some starting points for investigating this very enjoyable work's implications for NKS:

1. Do the coarse-grainings of irreducible CAs often make useful/interesting predictions about their behavior, or do they usually just strip away all of the complexity?

2. The NKS book sets up Rule 110 to simulate a tag system by representing information in "coarse" localized structures. Indeed, the schematic on page 683 might be considered a visual coarse-graining of the rule's evolution. Can we find a systematic coarse-graining rule along the lines of Israeli and Goldenfield that can evolve these structures -- and thus achieve universal computation -- with less clutter?

3. Can we find any examples of an interesting CA being coarse-grained by a Class 3 CA that would be at all relevant to the question of whether Class 3 CAs are or can be universal?


Posted by: Jason Cawley

See also - http://forum.wolframscience.com/sho...s=&threadid=515

A slightly different form of Mike Lin's suggestion (3) does seem possible, in the case of rule 54 for example. Course graining a class 3 can reveal useful information structures that might well be relevant to the class 3 question.




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