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.
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
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.
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
Valid point: it depends what invariants you're trying to construct. Considering only the odd elements of the sequence does yield a slightly different set of insights compared to other approaches. (9 / 28 / 52 still describe a counterexample to the proposed invariant, even in this scheme.)
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.
Collatz, busy-beavers, and algorithmic information theory are all related. To the extent they offer insight into the sparseness or density of irreducible complexity in the space of all computation.. this has many implications for what can be computed efficiently, what can be learned efficiently, program-synthesis, what can be analyzed "at a distance" without just trying it and potentially needing to wait forever, etc.
Whether it will say anything very significant practically or only philosophically is a different question. Maybe it is something like the discovery of transcendentals.. finding out that most of the number line won't have a tidy algebraic closed-form isn't exactly a make-or-break deal for the program of mathematics itself, and it also doesn't matter much to people who are doing engineering
Hailstone numbers has been a popular subject in computing circles since forever. Not much practical application, just a very simple, but curious construct.
> Does this have some significance for back propagation or something
You're right!
What could darn possibly matter these days, in the whole entirety of the realm Mathematics, if it does now somehow have a measurable impact on backprop ?
No you didn't misunderstand, I think. I thought there were some values that went on forever!
edit: however we could consider the weaker definition of "forever", and consider there are some outliers that go on "for a long time" per post title, probing structure with these loops and spokes. :D
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 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_co...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.
The paper (2019): https://arxiv.org/abs/1909.03562
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
Not to say their statement is true but I don't see any reason to count the initial zeroes.
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
Valid point: it depends what invariants you're trying to construct. Considering only the odd elements of the sequence does yield a slightly different set of insights compared to other approaches. (9 / 28 / 52 still describe a counterexample to the proposed invariant, even in this scheme.)
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.
Collatz, busy-beavers, and algorithmic information theory are all related. To the extent they offer insight into the sparseness or density of irreducible complexity in the space of all computation.. this has many implications for what can be computed efficiently, what can be learned efficiently, program-synthesis, what can be analyzed "at a distance" without just trying it and potentially needing to wait forever, etc.
Whether it will say anything very significant practically or only philosophically is a different question. Maybe it is something like the discovery of transcendentals.. finding out that most of the number line won't have a tidy algebraic closed-form isn't exactly a make-or-break deal for the program of mathematics itself, and it also doesn't matter much to people who are doing engineering
Hailstone numbers has been a popular subject in computing circles since forever. Not much practical application, just a very simple, but curious construct.
Crazy how AI has infected every conversation these days.
> Does this have some significance for back propagation or something
You're right!
What could darn possibly matter these days, in the whole entirety of the realm Mathematics, if it does now somehow have a measurable impact on backprop ?
youtube link https://youtu.be/k-dtx8s2ehM
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
Except the Collatz Conjecture is almost certainly true, and there are no starting points that go on forever. Or did I miss the point of the analogy?
No you didn't misunderstand, I think. I thought there were some values that went on forever!
edit: however we could consider the weaker definition of "forever", and consider there are some outliers that go on "for a long time" per post title, probing structure with these loops and spokes. :D