I can equate Collatz conjecture's function to:

  1. If a string has an odd number of 1's append a 1

  2. If a string has an even number of 1's :

    a) copy the position of the 2's into a new 0 only string, and make them 1 then replace all the 2's in the original string with 0's

    b) take all 1's and replace them with the string for one half. Noting these sum to 2 at every second 1's position so ex. 1010... becomes 120... then starting over with the 1's between placements of 1's and a 2 every second place a one resides and repeat.

    c) add the resulting base 3 strings from a and b ...

This in some ways reminds me of busy beaver, so I was wondering: What is known about it ?

  • $\begingroup$ I think De Hol (forgot her first name) wrote a paper on 2-tag systems that compute C.S, there are $3$ production rules. You should also look at Cellular Automata, there are two elementary rules that computes the C.S.s $\endgroup$
    – user366820
    Commented Aug 9, 2021 at 0:34
  • $\begingroup$ Yeah I once was told this base version, and the automata version, show by theorem that it's true? $\endgroup$ Commented Aug 9, 2021 at 0:37
  • $\begingroup$ I think it's very hard, but may be reachable. We only guess in which branch of mathematics it will be solved or not (undecidable), or a new "field" one. Nobody knows. I have a feeling more can be said in Graph Theory, but in those areas like $2$-tag, automata approaches in simple systems that produce complex behavior. $\endgroup$
    – user366820
    Commented Aug 9, 2021 at 0:45
  • $\begingroup$ Actually, I think that a proof would have to have very logical reasonings, no room for errors, very fine tuned for exactly what this problem is all about. But still... $\endgroup$
    – user366820
    Commented Aug 9, 2021 at 0:52


You must log in to answer this question.

Browse other questions tagged .