Registered: Aug 2003
Posts: 100

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

Report this post to a moderator | IP: Logged

Registered: Nov 2003
Posts: 14

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?

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

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.

Report this post to a moderator | IP: Logged