I have a Cellular Automaton that of any initial integer (initial condition of the automaton) generates states of Collatz sequences. The neighbourhood of the automaton is shaped like an L-tetromino (including two time-states). The (quiescent) background is represented as $0$ (the state zero). The other $1$-state (on-state) generates active border on the left side during the generation of the automaton. The border is the interesting part because that is where the "currect" generation either increases (is odd), are still (is odd) or decreases (is even). My earlier post on the matter was closed due to my question being unclear.

I have found out that if I can write a paper about this (or get somebody to help me writing it - helping me with terminology and such), we could represent the ($3n+1$) Collatz-problem with an Cellular Automaton (or Adaptive Cellular Automaton), and someone could approach the problem from that standpoint; like for example, Matthew Cook proved that Rule 110 was Turing Complete (i.e universal); and an undergraduate from UK proved that a $2,3$ Turing machine was universal. I have a feeling that we might perhaps find out if the conjecture is true, false or unprovable by solving some properties of this automaton.

Since now the Collatz Conjecture is represented as a Cellular Automaton, I think we can make one or more conjectures; one that either indirectly proves or disproves the conjecture, or one that gives us some information about its behaviour or if its undecidable. I have not been able to reach out to the mathematics community with my Cellular Automaton on the Collatz conjecture, and I don't know if it allready exists (that is; if someone else have allready done it), I have not yet found a paper that looks similiar to my representation (on an binary integer lattice using L-tetromino shaped neighbourhood).

On the automaton: I think convergence is difficult to prove in a Cellular Automaton, but it might be possible depending on the neighbourhood, rule and CA-setup perhaps. I think maybe proving that the paths that the neighbourhood takes (Transition Function) reaches some boundary (or not) will prove that the Conjecture is true or not. It's hard for me to actually describe what I mean about this. Please, if anyone have tried this before? I would like to hear more about it. Anyone how knows about information, or a paper on this specifically I would like to know.

My question is; does there allready exists a conjecture on the Collatz in the form of an Cellular Automaton, and such that if something about it can be proven true or false - it will also prove if the original Conjecture is true or false?


Example of space-time diagram of the Cellular Automaton showing odd numbers only (leaving out the shift right rule):

enter image description here

  • $\begingroup$ You may or may not have already tried a Google search and found, for example, CS StackExchange question 11611 "What is the 'nearest' problem to the Collatz conjecture that has been successfully resolved?". $\endgroup$
    – Somos
    Commented Jul 26, 2018 at 23:57
  • $\begingroup$ No, these things are of interest. Thanks. $\endgroup$
    – user366820
    Commented Jul 27, 2018 at 0:04
  • 1
    $\begingroup$ FWIW, this is still rather unclear - you've put the words 'Collatz conjecture' and 'cellular automaton' together but you haven't really defined your automaton at all or explained how you think it models the Collatz problem. Being much more specific, possibly with an example, would be really useful here. $\endgroup$ Commented Jul 27, 2018 at 0:30
  • $\begingroup$ Sorry. I'll try describe it better tomorrow since Im going to sleep soonish. I can describe it shortly with a few words here first though. It models the Collatz problem like this: Every configuration the CA generates produce next integer in sequence. By binary values, much like rule 110, it produce output on the left side, so most significant bit is on the far left where the last '1'-bit is located. Like any other Collatz function each iteration is equal to each the CA-configuration. The CA is a 2-state 4-state neighbourhood (L-shaped with 2-time states at the same time). $\endgroup$
    – user366820
    Commented Jul 27, 2018 at 0:43
  • 2
    $\begingroup$ @NaturalNumberGuy 'Simple', but that makes it cease being a cellular automaton. Indeed, I don't think there's even a CA that can operate on the binary representation of a number $n$ to produce $n+1$, for a subtle but vital reason: CAs by their nature are local in operation; a cell's value in a new generation can only depend on the values of a fixed finite neighborhood of cells in the previous generation(s). But operations such as addition and (non-power-of-two) multiplication are innately nonlocal on binary representations; they can depend on bits arbitrarily far away. (Consider 111111+1) $\endgroup$ Commented Jul 27, 2018 at 1:15

1 Answer 1


The Collatz problem can be mapped even more simply to a cellular automaton using base 6, because division by 2 in base 6 is extremely similar to multiplication by 3, and there is no problem of cascading carries. It is fairly easy to create a 7-state automaton whose neighborhood is simply two adjacent cells in the previous generation. The 7 states correspond to the 6 digits of base 6, and a null state to mark the edges of the computation. Someone coded a base 6 cellular automaton representation of the Collatz conjecture on wolfram.com in 2011: https://demonstrations.wolfram.com/CollatzProblemAsACellularAutomaton/


You must log in to answer this question.