Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Cellular Automata, the Collatz...

Cellular Automata, the Collatz Conjecture and Powers of 3/2

Jarkko Kari, Cellular Automata, the Collatz Conjecture and Powers of 3/2. In: Hsu-Chun Yen, Oscar Ibarra (Eds.), Developments in Language Theory - 16th International Conference, Lecture Notes in Computer Science 7410, 40–49, Springer, 2012.

Abstract:

We discuss one-dimensional reversible cellular automata F×3 and F×3/2 that multiply numbers by 3 and 3/2, respectively, in base 6. They have the property that the orbits of all non-uniform 0-finite configurations contain as factors all finite words over the state alphabet {0,1,…,5}. Multiplication by 3/2 is conjectured to even have an orbit of 0-finite configurations that is dense in the usual product topology. An open problem by K. Mahler about Z-numbers has a natural interpretation in terms the automaton F×3/2. We also remark that the automaton F×3 that multiplies by 3 can be slightly modified to simulate the Collatz function. We state several open problems concerning pattern generation by cellular automata.

BibTeX entry:

@INPROCEEDINGS{inpKari_Jarkko13a,
  title = {Cellular Automata, the Collatz Conjecture and Powers of 3/2},
  booktitle = {Developments in Language Theory - 16th International Conference},
  author = {Kari, Jarkko},
  volume = {7410},
  series = {Lecture Notes in Computer Science},
  editor = {Yen, Hsu-Chun and Ibarra, Oscar},
  publisher = {Springer},
  pages = {40–49},
  year = {2012},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication