Does this have some significance for back propagation or something, or is it just an interesting trick of arithmetic? //not that it needs to have a technical use, it's still neat.
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
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
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.
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.
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.
10 comments
[ 3.2 ms ] story [ 31.0 ms ] threadIt would seem simple, but many simple iterative calculations get us to Turing machine territory regarding computability.
Some kind of structure there that Collatz probing is sketching
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.
But I’m interested in hearing the counterarguments that Collatz likely is provable within PA and why this would be the case.