You convert any computer program P into a start number n_0, then run the 3n+1 (or 5n+1) process to get the sequence n_0, n_1, n_2, \ldots
Meanwhile, read off the program’s execution trace (and output) from that sequence.
Thoughts?
1 Like
This certainly computes something, but maybe the question is: what can you compute using 3n+1 trajectories. I think that if you want it to be Turing complete, you’ll need to have some computations that never halt, which I assume corresponds to nonterminating 3n+1 trajectories. So it sounds like showing this would require disproving Collatz conjecture, heh.
Sounds right!
Supposing for the moment the 3n+1 conjecture is true … or maybe suppose an even stronger version like, “every start number m goes to 1 within 100 \log m steps” … then what might 3n+1 still be able to compute?
Is there any interesting O(\log n) function, say, that 3n+1 can implement?
For example, could it compute \gcd(a, b) if a and b were suitably coded up in some start number m?
Or … if that seems unlikely … how about proving: “If the Collatz conjecture is true, then \gcd(a, b) can’t be computed by 3n+1.”
(An analogy might be “A finite-state acceptor cannot detect whether unary input 1^n is prime.”)
Deep questions here, I know … though at least they’re well-formed? 
The hard part is 3n+1 sequences are random-looking, but not random. And I seem to remember some quote like, “Why does it have to compute something? Can’t it just compute?”
Yet my gut feeling is there’s some untapped energy source in the 3n+1 process!
Here we should mention the Wang tile interpretation of the 3n+1 process, due to @cosmo and Matthew Cook, that I will try to summarize (@cosmo are you here?). According to it, we may view this process as a sort of cellular automaton on a 2D regular grid that evolves either downward from a horizontal alignment of cells, or leftward from a vertical alignment. Each cell can be in any of 6 different states, provided that the contiguous egdes of all pairs of neighboring tiles have the same color (out of 3 colors).
What is really interesting is that this automaton has been shown to convert the base 3 (vertical) representation of any arbitrary number into its base 2 representation (horizontally). The required number of steps for this conversion to be completed is exactly the size of the number in base 2 (as far as I understand…). In the same time, this automaton also computes the base 6 and base 3/2 representations along the diagonal directions. Thus, it seems unlikely that we can compute other things like a prime factorization, unless it can be diverted from its primary function and do something else in the long run… Plus the fact that is expected to “halt” within a number of iterations at most 30 times the initial number of digits in base 2.
See this post for more details.
1 Like
This question was really the heart of the motivation of the Collatz part of my PhD thesis (first screenshot is context, second screenshot is exactly this question):
On top of what @oros said I will add that together with Matt Cook and Damien Woods we proved that the same 6 tiles that simulate Collatz can simulate aribitrary computers if you allow your assemblies to have holes (which is a big caveat because Collatz assembly do not have holes):
1 Like
This way to visualize computation is really amazing.
The “coding up” of the input is done by arranging tiles along an x-axis and a y-axis, and the computation fills in the quadrant.
And there’s even the concept of doing this in a wet lab!
1 Like
@cosmo 95% chance I have this wrong – appreciate any corrections or comments! In my reading of the CQCA paper on base conversion, the same quadrant-filling automaton can be run in either of two modes:
- Put m (in binary) on the first row, and all zeroes on the first column. Then successive rows will show odd Collatz iterates of m.
- Put b (in base 3) on the first column, and all zeroes on the first row. Then successive columns will yield the base 2 form of b.
So the same machinery that can do Collatz can be re-purposed to do base conversion, which is a total surprise.
The “direct hijack” procedure I was imagining was to convert a number b from base-2 to base-3:
- Pick a start number m with initial parity sequence b (no problem, there are zillions).
- Run Collatz for \lceil \log_2 b \rceil steps.
- “Read off” the base-3 form of b from the generated trajectory.
But I think maybe that’s a totally different story, and I’m not clear if that could be done.
1 Like
Not exactly since (amazingly) successive columns will yield Collatz iterates of m in base 3. The base 2 conversion of m is on the last row (of the initial rectangle).
The base-3 conversion of the initial number is encoded in the backward iterations! Every odd predecessor encodes one digit. You may object that there are many different ways to go backward, but you can simply pick one (with sufficiently many odd terms) and you’re done
@cosmo can correct me if I’m wrong …
2 Likes
I agree with @oros answers
The direct hijack is from base 3 to base 2, start with a base 2 number and compute Collatz on it in a “CQCA fashion” (i.e. well-tabulated and keeping tracks of carries) and you will see appear your number converted in base 2 after #bits iterations, hopefully this figure summarises the situation:
The easy rectangle is base conversion (i.e. it can be predicted really quickly, this is what “NC1” approximately means), and the hard rectangle is the one that generates the parity vector, for which we don’t have a better prediction algorithm than just simulating Collatz.
(Note that the tiles are just a finer-grained version of CQCA.)
1 Like
Got it!
The automaton converts 119_3 (initialization for right column) to 119_2 above the black line.
As you keep going down, the blue arrows show the first 9 bits of the parity sequence (111001000).
In the (larger) portion of the Hard Rectangle not shown, which extends further to the left, the blue arrows keep on going: 111001000110011010010001.
That’s super-clear, and it puts @oros nice phrase “primary function” into visual context. The Easy Rectangle shows the automaton doing its primary function (base conversion).
Now … if I paid $9.99 for an Ubik-brand base converter and it kept running (for an unpredictable amount of time) after giving me its output, I might run Norton Antivirus on it!
1 Like
It’s hard to defend the thesis that there’s untapped dark energy in 3n+1 trajectories that might be harnessed for solving hard computational tasks, but the base converter is heartening!
Monks built a register machine (coded in Fractran) to do 3n+1. This is his machine going from 7 \rightarrow 11 \rightarrow ... (Collatz numbers appear as exponents in pure powers of 2):
2^7 - 2^5 3^1 11^1 - 2^5 3^1 - 2^3 3^2 11^1 -
2^3 3^2 - 2^1 3^3 11^1 - 2^1 3^3 - 3^3 5^1 -
2^3 3^2 17^1 - 2^3 3^2 5^1 - 2^6 3^1 17^1 -
2^6 3^1 5^1 - 2^9 17^1 - 2^9 5^1 -
2^{11} - 2^9 3^1 11^1 - 2^9 3^1 - … - 2^{17} - … - 2^{26} - …
He stores computational state in the exponents of primes 2, 3, 5, … 17. Each step manipulates the register contents with simple multiplication (by a fraction), no more that +1 jazz.
I did similar but only with 2, 3, and 5. Here is the Collatz trajectory 3 \rightarrow ... \rightarrow 1.
2^3, 2^2 3^1 5^3, 2^1 3^1 5^6, 3^1 5^9, 5^{10}, 2^1 5^9,
2^2 5^8, 2^3 5^7, 2^4 5^6, 2^5 5^5, 2^6 5^4,
2^7 5^3, 2^8 5^2, 2^9 5^1, 2^{10}, 2^8 3^1, 2^6 3^2,
2^4 3^3, 2^2 3^4, 3^5, 3^4 5^1, 3^3 5^2, 3^2 5^3, …
2^6 3^5, 2^4 3^6, 2^2 3^7, 3^8, 3^7 5^1, 3^6 5^2,
3^5 5^3, 3^4 5^4, 3^3 5^5, 3^2 5^6, 3^1 5^7, 5^8, …
2^4, 2^2 3^1, 3^2, 3^1 5^1, 5^2, 2^1 5^1, 2^2,
3^1, 5^1, 2^1
The intermediate computation of the above machine is pretty much just focused on getting from 2^3 to 2^5 (then from 2^5 to 2^8, etc). The more interesting unpredictable action happens at the “zoom out”, jumping from one Collatz (pure-power-of-two) number to the next.
Even though some register machines can compute gcd, and some are universal computers, it’s hard to argue that this particular three-state register machine can compute much beyond 3n+1 … but at least it increments, decrements, and tests registers @cosmo also has many such automata!
Pretty neat actually — same function showed up here 6 months ago too:
1 Like
I decided to remove the post because in hindsight I thought it was actually pretty silly and not really related to the Collatz Conjecture. I’ll put it back:
Sorry for my silliness again, but I think the Collatz Conjecture might be a tiny part of a larger system. A system that can calculate and find prime numbers.
The conjecture:
F uneven = 1N + P
F even = /2
The rules:
- Start with F = 1 but you can use any positive number < P
- If the F = 1 cycle contains (P - 1) / 2 amount of uneven numbers: P is a prime number.
(11 - 1) / 2 = 5 uneven numbers, 11 is a prime number.
(33 - 1) / 2 = 16 uneven numbers, 33 is not a prime number.
I tried all uneven numbers from 1 to 100 and found these numbers which are all prime numbers:
Surely this needs way more testing with bigger numbers, but it takes me way too much time with just my calculator and art programs. Maybe someone could create a script of some sorts.
If the formula is correct it could also use some adjustments to make it find the other prime numbers as well. But maybe that is not what it is supposed to do and these numbers are special. I don’t know, it is just something I wanted to leave out here, something for you professional mathematicians to think about.
2 Likes
That’s interesting, Stacey, and seems to work, although the algorithm is amazingly simple!
Here is a sketch of proof:
Suppose you get a cycle with (P-1)/2 odd terms, namely, all odd integers below P. Then it contains all even integers below 2P. From this, it can be shown that the order of 2 modulo P is equal to P-1 (because you return to 1 after exactly P-1 divisions by 2). By applying Euler theorem, we obtain that \phi(P)=P-1, where \phi(P) is the number of integers relatively prime to P below P.
So, P is prime.
3 Likes
Really cool stuff!!
Silly question but is that also the argument for why 1 generates a cycle? Or is there a simpler argument?
By induction, we can show that the odd terms in the trajectory of 1 cannot exceed P-2, as soon as P is odd. The reasoning is similar.
2 Likes
From Maksandchael on bbchallenge’s discord:
What about mersenne primes?
The above algorithm is not fast enough for large primes, with hundreds of digits.
In the particular case of Mersenne primes, we have the much faster Lucas-Lehmer test, which is why these numbers hold the record by a wide margin.
2 Likes
I suddenly feel a little proud that I came up with this on my own, I think it was last year. But I am pretty sure more people came up with this conjecture in the past without me knowing about it.
However, I just can’t find the relationship that this conjecture has with the Collatz Conjecture besides the thought that maybe the Collatz Conjecture and other xN+x conjectures could be data cards for filtering out uneven numbers for similar functions like this.
2 Likes
Its a really nice result!!
2 Likes