Wolfram Computation Meets Knowledge

Wolfram Summer School

Alumni

Paul-Jean Letourneau

Summer School

Class of 2006

Bio

Paul-Jean Letourneau received an honors degree in physics from the University of British Columbia in 2003, with a specialization in biophysics and computational physics. Throughout his degree he worked for several industrial and academic laboratories around North America, where he made original theoretical and experimental contributions to real-world problems in medical imaging, protein folding, geophysical data analysis, and DNA-protein interactions.

Paul-Jean attended the 2004 NKS Summer School, where he completed a pure NKS project on elementary cellular automata with memory. He was then invited back to the 2005 Summer School as an instructor, lecturing on Mathematica programming and completing a second Summer School project based on classifying fluctuations in simple programs. Paul-Jean was an invited speaker at the 2005 Midwest NKS Conference and the NKS 2006 Wolfram Science Conference, and he returns to his role as an instructor at the 2006 Summer School.

Paul-Jean recently received a master’s degree in theoretical physics from the University of Calgary, with a thesis project entitled “Statistical Mechanics of Elementary Cellular Automata with Memory.”

Project: Enumeration and Analysis of Boolean Networks

Boolean networks are an oft-used model for gene interactions, but small Boolean networks appear to never have been explicitly enumerated and studied. This project is an endeavor to enumerate and study the state transition graphs of simple Boolean networks. The project will progress in four phases.

Phase 1: Two-Input Cellular Automata

In phase 1, I will study the state transition graphs of two-input cellular automata, where the inputs to each cell come from itself and its right neighbor. There are 16 possible rules of this kind, and 7 fundamentally different ones after removing cases that are left-right reflections and black-white inversions. These rules include logical primitives AND and OR, along with several others. Periodic boundaries will be used. For width N, there are 2^N possible states, and therefore 2^N points in the state transition graphs. The goal is to characterize the state transition graphs that appear. One measure is the number of disjoint attractors there are in the state transition graph. What can one say about the infinite size limit by looking at successively larger N? The networks formed by two-input cellular automata are always cyclic.

Phase 2: Two-Input Cellular Automata with Non-Local Connections

In phase 2, I will introduce non-cyclic networks into the two-input setup. This will be done by changing the way cells are given as input to other cells. How do the state transition graphs change when one introduces non-locality in the connections?

Phase 3: Two-Input Cellular Automata with Inhomogeneities

The next step is to investigate the effect of using different rules for different cells. For example, let the center cell use the logical rule OR (rule 14 in the 2-input rule enumeration), and all other cells use AND (rule 8). How does the state transition graph change from the all-AND case? As one increases the number of OR cells, is there a regular change in the number of disjoint attractors in the state transition graph?

Phase 4: Two-Input Cellular Automata with Inhomogeneities and Non-Local Connections

In phase 4, I will enumerate boolean networks of a given number of nodes N, using different rules at the different nodes. The goal is to look exhaustively at all networks of a given size, starting from the smallest and the simplest ones. With N nodes, there are in general 2^(N^2) ways of connecting them in a network. Many of these will likely be equivalent due to symmetries. It is important to recognize as many of these symmetries as possible in order to obtain more tractable exhaustive searches.

Favorite Four-Color, Radius-1/2 Rule

Rule chosen: 490694802

My favorite four-color, radius-1/2 rule number is 490,694,802. I found it doing a search for rules with interesting boundary growth from a simple initial condition. This rule supports some interesting persistent structures with at least some variety in speeds, which have some interesting interactions. The diagram shows a collision between two regions.

To find this rule, I simply found the left and right boundaries when starting from a simple initial condition, and plotted the position of the boundaries over time. I inspected the graphs of a couple of thousand randomly chosen rules, and ended up with 57 that had interesting boundaries.