Wolfram Science

Live Experiment Notebooks

The notebooks from Stephen Wolfram's live experiment at NKS 2007 last night are now available!

Download NKS2007-LiveExperiment-01.nb (76.0K)
Download NKS2007-LiveExperiment-02.nb (5124.2K)
(Right-click and select "Save Target As" or "Save Link As")

Stephen explored various interesting properties of ECA rules 18, 22 and 122.

Jason Jacobs: Substitution Systems Design Process

Pure NKS lecture series

Jason Jacobs describes the design of a substitution system to solve an interesting problem

Can you design a system that, given information about the past, present and future, returns information about the present without affecting the past, present or future. Jacob's solution uses a rewrite automata system in a finite 3D space.

Jason demonstrated various rules in this finite space with a tool he created for designing, running and recording rules.

Fritz Obermeyer: Mapping the Space of Programs, Searching the Space of Languages

Pure NKS lecture series

Fritz Obermeyer discusses mining the space of programming languages

Given a simple programming language family like lambda calculus, Fritz asks: what are the simplest few program behaviors? These behaviors form a basis that seems big but really isn't all that big. In an more abstract view, we can consider the behavior space of programs, and define a bigger map, and Fritz argues that this is the worthwhile space to map.

Since programs are elements of an algebra, like constants, binary operations, and equations and/or inequalities, a first starting place for this map is to try computational algebra methods. Fritz gave an example of making a map with the Todd-Coxeter algorithm. In theory, equivalence is undecidable, but in practice, given enough computation, equivalence is largely decidable (Fritz cites 96% in one particular case).

Then in the space of programs, Fritz can calculate the shape of an algebra of programs using Kolmogorov complexity. In order to visualize the space, Fritz posed the space as an eigenvector problem and is able to visually illustrate the difference in different programming styles in a program space. Through proper definition, the space of programs is a Reimannian manifold.

Potential applications of thes techniques include program simplification, using a database of simple rewritings, or software analysis, refactoring based on spatial proximity. It is also possible to program by searching.

Fritz's analysis shows that the average over all languages is simpler than any one.

Kovas Boguta: "Dialectical Cellular Automata"

Kovas Boguta presented a new system called "dialectical cellular automata" wherein two cellular automata update with information about each others states spliced in. Each CA follows one rule, but the rules update based on the state of cells in the other CA at the same position. In this way, the CAs form a kind of dialogue where information is shared at each step. He had some interactive examples (Demonstration forthcoming) and also showed an array of the dialgoues between rule 30 and all other ECA rules. He presented models of interacting programs as alternatives to making NKS studies more complicated through more complicated rules and/or initial conditions." Of his many arguments for the study of these types of systems, the one that gave me the most thought was that "computation is a process not an in-out mapping," indicating that it is more difficult in the real world to determine the boundary between program rules and initial conditions. What is an isolated physical system computing except for what the laws of physics predict for the state of the system at a later time?

Emmanuel Sapin: "On Discovering Gliders and Glider Guns with Evolutionary Algorithms"

Sapin's project was to find universal CAs with the game of life. He had many interesting example configurations where he was using so-called gliders and glider guns to model streams of information. He would configure the initial states with glider guns whose paths intersected. Gliders that collided would be annihilated, which in some cases would create gaps that would allow other gliders to pass through a stream. Sapin claimed that these systems represented AND logic gates. One could easily imagine universal computation being done by certain configurations of these glider guns.

Sapin also has some interesting tools for creating conditions in his Game of Life. With a contextual menu, he could create a field of random obstacles and set up some glider guns to fire against them and interact.

Slides for Matthew Szudzik's Presentation

Here are the slides from my presentation, "An elegant pairing function" (in Mathematica format).  Download ElegantPairing.nb

Kohji Tomita & Haruhisa Kurokawa, "Two-State Graph-Rewriting Automata"

Posted by Joe Bolte.

By coincidence, the topic of this presentation seemed similar to Jesse Nochella's idea. However, the nodes in the networks here had internal states, which vastly increase the number of rules possible. In addition, the presenters were concerned with evolving the branch structure, which the previous presenter did not consider. The presentation contained a great deal of information in the form of graphs, which are difficult to summarize here, so if you're interested in this topic, you can download a PDF of the talk. Abstract.

Jesse Nochella, "Cellular Automata on Networks"

Posted by Joe Bolte.

Jesse presented an idea for cellular automata running on networks which generalizes the idea of the dimensions on which the CA runs. Basically, one generates a rule for whether a node will be black or white on the next step, based on the percentage of the nodes neighbors that are black. Since one can have any number of neighbors for each node, or even vary the number of neighbors from node to node, his idea allows the creation of cellular automata with fractional dimensions. Abstract.

Todd Rowland, "Two-Dimensional Totalistic Code 52"

Todd Rowland took us on an in-depth tour of two-dimensional 5-neighbor totalistic Rule 52. This is one of the more flexible rules out of the 64 possible rules of its type. Rule 52 emulates more elementary cellular automata than any other 5-color totalistic rule. Todd showed some of the emulations that he found through brute force searching for similarities between this rule and one-dimensional ECAs. Abstract.

Live Computer Experiment by Stephen Wolfram

Posted by Joe Bolte

After the Q&A, Stephen Wolfram performed a live computer experiment from scratch. He chose to search for complex behavior in a class of systems called step registers. Starting from a blank Mathematica notebook, Wolfram generated a ruleset and combed through it for examples of complex behavior, first using a two-neighbor rule and then a three-nighbor rule. You can see that in the two-neighbor case rules 6 and 9 yielded complex behavior and in the three-nieghbor case, rules 90 and 165 were the interesting results. Wolfram had an intuition that rules 90 displayed additive behavior, but he was not able to demonstrate anything before time ran out. Please take a look at the Mathematica notebook of the experiment.

Update: Christopher Haydock noted a problem with the notebook and submitted a corrected version, with the code extensively refactored to be clearer for those following along at home. Thanks Chris!