Bio

At Wittenberg University, Springfield, Ohio, Brenton Bostick is pursuing his Bachelor of Science degree, majoring in Computer Science with minors in Mathematics, Physics and Computational Science. In the past he has conducted mathematical research on iterated exponentiation and has presented his work on interpolation polynomials at the 13th Annual Argonne Symposium For Undergraduates In Science, Engineering and Mathematics. His computational research has focused on generalized run-length encoding and cellular automata algorithms. He presented a paper on “Parallelizing the Game of Life” at the 2002 Graduate Student Workshop and Conference of Ohio State University’s Supercomputer Center. Brenton plans to obtain a PhD in Computer Science, afterward moving on to either independent consulting or research into symbolic computation or discrete modeling.

Project: An NKS approach to the 3n+1 problem

I studied the 3n+1 problem using approaches characterizing ideas from NKS. The 3n+1 problem defines a function f[n_]:=If[EvenQ[n], n/2, 3n+1] and asks the question: do all integers eventually iterate to 1?

A cellular automaton was built that computes iterations of the function. The cellular automaton given in the book has a few draw backs that warrant a new one: it operates in base 6, an unfamiliar base for many people, and it constantly moves to the right which requires an outside operation to read the number once computed. However, there are advantages: its rule table is stated simply in one update rule in Mathematica and works in only 7 colors. It also computes all digits of any one iteration in parallel.

My CA works in base 2. It has 9 colors. It has a fixed “binary point” color that acts as an anchor. Its rule table is stated minimally. It takes 2 time steps to compute a bit for each iteration, but multiple bits are computed in parallel.

Casting the problem into the realm of cellular automata shifts it from a global question of digit behavior to a local one. One interesting yet straightforward result is that only a small number of combinations of colors are possible. Future work will include statistical analysis and pattern recognition on local structures in the CA.

Favorite Three-Color Cellular Automaton

Rule Chosen: 2367504716536

Reason: I wanted to search for an interesting k=3, r=1 CA rule systematically. I decided to compose 2 k=2 rules and, go from there. I started with all of the rules with 1’s or 0’s emulating rule 45 and all of the rules with 2’s or 0’s emulating 90, with all rules with 1’s or 2’s being randomly generated. I decided I didn’t like the alternating background, so I flipped the {1,1,1} sub-rule to 1. My rule demonstrates many combinations of colors that generate gliders, thus allowing a very dynamic and active landscape when started with random initial conditions. I doubt if my rule is capable of class 4 behaviour, the gliders don’t seem to be sufficient.

Additional Information

Bostick, B. “An NKS Approach to the 3n+1 Problem.” Presentation at NKS 2004, Boston, MA, 2004. [abstract]