The closely related function Col' which also divides 3n+1 by 2 in the odd case, is concisely represented by the 65-bit lambda calculus term λ1(λλλ31(λλ2(421)))(λλ1)1(λλ1) operating on Church numerals [1]. It starts from the pair of numbers n and 0 and then performs n iterations of swapping the numbers after incrementing the first. Its lambda diagram is
I especially like how he highlights that Collatz conjecture shows that a simple dynamical system can have amazingly complex behavior; also 3n-1 variant has two known cycles - so "any proof of the Collatz conjecture must at some point use a property of the 3n+1 map that is not shared by the 3n-1 map." And this property can't be too general either - questions about FRACTRAN programs (of which Collatz conjecture is a special case) can encode the halting problem.
In case people don't know the Collatz Conjecture, It's based on a simple rule: take any natural number n. If it is even, divide it by 2. If it is odd, multiply by 3 and add 1. The conjecture states that no matter what number you start with, you will eventually reach the number 1.
It would seem simple, but many simple iterative calculations get us to Turing machine territory regarding computability.
As a non-mathematician, I’m confused why so many people think the conjecture (whether true or false) is provable within PA. To me, it seems like something that would be very nicely just right outside the boundary of PA’s capability, sort of like how proving all Goodstein sequences terminate requires transfinite induction up to ε_0. Add that to the fact that the Collatz Conjecture seems to fall in the same “category” of problem as the Turing machines that the Busy Beaver project is having a hard time proving non-halting behavior of, and the heuristic arguments all seem to point to: Collatz is independent of PA.
But I’m interested in hearing the counterarguments that Collatz likely is provable within PA and why this would be the case.
The Collatz conjecture is "obviously" (i.e. probabalistically) true, so it's frustrating to not be able to turn that into a proof. PA doesn't matter, there's no known approach to proving it with stronger theories either. Of course many other propositions like the twin prime conjecture are in the same situation.
Goodstein's theorem by contrast is obviously provable in slightly stronger theories than PA, and it involves a fast-growing sequence which suggests it's out of weaker theories' reach. In fact it encodes ordinals up to eps_0 in a natural way, so its equivalence to CON(PA) is unsurprising. The Collatz conjecture is nothing like that. It's beguilingly simple by comparison.
Someone has also noticed another curiosity:
The number of bits of the biggest number (in binary notation) in a path is less than the number of bits of the initial number (in binary notation) * 3 + 1
If that were true, then every number would lead to a cycle (possibly a different one from 1-4-2). It would make the decision problem (whether a given initial number leads to 1) decidable, and the Collatz conjecture finitely refutable.
This isn't true. Take 9_A = 1001_2. 28_A = 11100_2, which is 5 bits long (3 set). The biggest number in this path is 52_A = 110100_2, which is 6 bits long (3 set). 5 ≯ 6, and 3 ≯ 3: neither of my interpretations of your statement holds.
There is another interpretation, reading "bits" as "set bits" and assuming that textual description (especially the operator "of the") has a higher precedence than multiplication, then your initial number is 9 with 2 bits set, and the largest number is 52 with 3 bits set, and 3 < 2 * 3 + 1 = 7.
What I understood was:
9_A = 1001_2 needs 4 bits, set or not set as the minimum length of the binary representation.
52_A = 110100_2 needs 6 bits
6 bits is less than 4*3+1=13 bits
Readit News
I especially like how he highlights that Collatz conjecture shows that a simple dynamical system can have amazingly complex behavior; also 3n-1 variant has two known cycles - so "any proof of the Collatz conjecture must at some point use a property of the 3n+1 map that is not shared by the 3n-1 map." And this property can't be too general either - questions about FRACTRAN programs (of which Collatz conjecture is a special case) can encode the halting problem.
If you haven't seen it, FRACTRAN itself is amazing - https://www.cs.unc.edu/~stotts/COMP210-s23/madMath/Conway87.... and the paper is pure joy to read.
It would seem simple, but many simple iterative calculations get us to Turing machine territory regarding computability.
But I’m interested in hearing the counterarguments that Collatz likely is provable within PA and why this would be the case.
Goodstein's theorem by contrast is obviously provable in slightly stronger theories than PA, and it involves a fast-growing sequence which suggests it's out of weaker theories' reach. In fact it encodes ordinals up to eps_0 in a natural way, so its equivalence to CON(PA) is unsurprising. The Collatz conjecture is nothing like that. It's beguilingly simple by comparison.
Deleted Comment
11100 == 111 == 11100000000, in terms of the next odd iteration
Even numbers don't really count in the process surely? All collatz does is essentially ignore those zeroes