3 ms·
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)))(
by tromp 11mo ago
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
┬───────────────┬──
│ ┬────────── ─ │ ─
│ ┼─────┬──── ┬ │ ┬
│ ┼─┬───┼──── │ │ │
│ └─┤ ┬─┼─┬── │ │ │
│ │ ┼─┼─┼─┬ │ │ │
│ │ │ └─┤ │ │ │ │
│ │ │ ├─┘ │ │ │
│ │ ├───┘ │ │ │
│ ├─┘ │ │ │
└───┤ │ │ │
└─────────┤ │ │
└─┤ │
└─┘
[1] https://github.com/tromp/AIT/blob/master/fast_growing_and_conjectures/collatz.lam https://github.com/tromp/AIT/blob/master/fast_growing_and_co...
- measurablefunc 11mo agoDoes it terminate for all n?
- tromp 11mo agoYes; the Col' function trivially terminates for all n, since Col n' is just (if odd n then 3*n+1 else n) `div` 2
- measurablefunc 11mo agoThat's good then. It shouldn't difficult to bootstrap that to the full Collatz conjecture.
- tromp 11mo agoSince the Collatz conjecture is not (known to be) finitely refutable, we cannot encode it as a program whose termination decides the conjecture. If the existence of diverging orbits were disproven though, then we could.
- measurablefunc 11mo agoThat's a good point & also surprising that such a simple dynamical process can not be proven one way or the other to be an instance of a terminating or non-terminating computation.
- deleted 11mo ago[deleted]
- im3w1l 11mo agoI thought that diagram was giving me crazy strong synaesthesia, but turns out it was subpixel rendering and it really did have color.