Bio

Guilherme Kronemberger is an electrical engineer who is currently a full-time student courtesy of the Brazilian’s National Counseling of Scientific and Technological Development. He expects to receive his MSc in electrical engineering in 2007 from Mackenzie Presbyterian University in Brazil. He is also working on a bachelor’s degree in comparative literature in Portuguese and German at the University of São Paulo. His interest in mathematics began in 1998 while taking a technical electronics course at São Paulo’s State Technical High-School.

Project: Search for Reversible Cellular Automata in 2 Dimensions

Cellular Automata can be used for modelling, prediction and analyses of data in many areas. With cellular automata, complex behavior can be achieved even from simple initial conditions. The behavior of a cellular automaton can have many properties, and one such property is reversibility. A cellular automaton is reversible if there is an inverse rule that transforms the output of the cellular automaton back into its input. This allows the cellular automata to run any condition forward or backward. This feature can be used, for example, in data compression or encryption. Studies of reversibilty suffer from a lack of information, and just a few rules are known that have reversibility.

The results of searches for reversible cellular automata in 2 dimensions were restricted to grids of different sizes, which had never been studied in the literature. The tests of reversibility were made for inputs of square blocks of sizes 1×1, 2×2, 3×3 and 4×4. Unfortunately, for inputs of blocks with more than 16 elements, the computer exceeded its 1GB memory limit. A few of the rules studied have the interesting property of being irreversible for specific inputs, which suggests a formalization of a reversibility degree. The automata that passed all tests only exhibited trivial behavior.

His work at the NKS Summer School was partially funded by Mack Pesquisa, the Mackenzie’s Presbyterian Institute foundation for research.

Favorite Outer Totalistic Three-Color Rule

Rule chosen: 1435266

I chose rule 1435266 because it has the following interesting behavior: if it starts with simple initial conditions (a central cell with a state equal to 1 and the others with the state equal to 0), then the pattern produced is nested; in all other five simple initial conditions (central cell 1 and the others 2, central cell 0 and the others 1, central cell 0 and the others 2, central cell 2 and the others 1, central cell 2 and the others 0) the information is lost rapidly. In a random initial condition, sometimes the information is lost too, but most of the time it rearranges the information in the beginning and some structures get stuck in the barriers that came from the iterations in the beginning. In this case the information continues to flow as they reflect when they reach the barriers, and even after 20,000 steps it doesn’ t die out. The information stuck in these barriers has a very interesting behavior: sometimes random, sometimes nested, and sometimes both. When these barriers don’t persist in the beginning of the pattern, it produces a nested or apparently random pattern that doesn’t die out. In this graphic, the green colors represent the cells with state equal to 2, the blue colors represent the cells with state equal to 1, and the white colors represent the cells with state equal to 0.