 |
Guilherme Kronemberger
Bio [2007]
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 Title
Search for Reversible Cellular Automata in
2 Dimensions
Project
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 1x1, 2x2, 3x3 and 4x4. 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 3-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.
|
|
|
