Wolfram Computation Meets Knowledge

Wolfram Summer School


Fernando Faria

Summer School

Class of 2007


Fernando Faria is a master’s student in electrical engineering, concentrating in computation engineering at Mackenzie Presbyterian University, São Paulo, Brazil. He was graduated in Information Systems from Mackenzie Presbyterian University in 2005. He also works as a systems analyst at the University of São Paulo. His Summer School experience was partially funded by the Fundo Mackenzie de Pesquisa from Mackenzie Institute.

Project: Solving the Majority Problem using Elementary Cellular Automata for Flexible Initial Conditions

The Density Classification Task (DCT) or, Majority Problem, consists of determining if a one-dimensional lattice with an odd number of binary cells has more 0’s or 1’s in its initial state. The evolution of the cellular automaton will converge to either 0’s or 1’s respectively after a certain number of steps.

It is known that no ECA rule solves the DCT non-trivially without further manipulation of either the rule or the input. In this case, non-trivially means that the rule does not consider all cells from the lattice in its neighborhood. Each initial condition has some rules that solve it, but there is no single rule that solves for all initial conditions without manipulation. The goal of this project is to find rules that solve the DCT for all initial conditions with minimal subsequent manipulation. In order to acheive this goal, we have used riffled inputs and have examined all possible rules up to certain length.

Favorite Outer Totalistic Three-Color Rule

Rule chosen: 9148480

My favorite rule is 9148480 because it shows a complex pattern combined with a fixed structure.

ArrayPlot[CellularAutomaton[{9148480, {3, {3, 1, 3}}}, {{1}, 0}, 500], ColorRules -> {0 -> Red, 1 -> Black, 2 -> Gray}]