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

    ┬───────────────┬──
    │ ┬────────── ─ │ ─
    │ ┼─────┬──── ┬ │ ┬
    │ ┼─┬───┼──── │ │ │
    │ └─┤ ┬─┼─┬── │ │ │
    │   │ ┼─┼─┼─┬ │ │ │
    │   │ │ └─┤ │ │ │ │
    │   │ │   ├─┘ │ │ │
    │   │ ├───┘   │ │ │
    │   ├─┘       │ │ │
    └───┤         │ │ │
        └─────────┤ │ │
                  └─┤ │
                    └─┘

Good background reading/watching - Terence Tao's "The Notorious Collatz conjecture" talk. https://www.youtube.com/watch?v=X2p5eMWyaFs Slides: https://terrytao.wordpress.com/wp-content/uploads/2020/02/co...

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.

The paper (2019): https://arxiv.org/abs/1909.03562

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.

youtube link https://youtu.be/k-dtx8s2ehM

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

It's like gravity, collisions, and interstellar objects. Some starting points escape and go on ... forever.

Some kind of structure there that Collatz probing is sketching

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.