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
Since 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.
That'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.
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.
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.)
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
At that point, the conjecture's just numerology: 27 takes 5 bits, and 9232 takes 14 bits (two shy of 3×5+1 = 16). 27 is the peak of the average ratio between start and maximum, because the +1s are so significant when the numbers are small: past that point, we're relying on extreme outlier behaviour to get each new high-score. Those only start showing up often enough to matter once we get into the thousands.
Plugging in values from OEIS A006884, it looks like the maximum ratio between the maximum and starting values goes down until around 4255, then picks up again, gradually increasing from there. Eyeballing the growth rate, I suspect there's a counterexample to this interpretation somewhere before 10^1000. (Does anyone have an element of A006884 greater than 2358909599867980429759? That's 140 bits maximum to 71 bits starting.)
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
There probably are some very large values that go on forever. It's interesting how the structure of numbers must change at some point. Seemingly just based on magnitude, but in huge scales, some kind of density of structures related to factors builds up and eventually hits a critical point. And "island of forever". Collatz island, above what we've tested. It will be cool to discover that. I wonder how big it is? Probably hundreds of millions of decimal digits. But it's likely dense enough that if you randomly search and land on the island, you probably have a good chance.
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.
I was just asking because I wondered if the high level of interest here was due to a connection with AI, not because I'm an AI evangelist. I tend to agree with you.
> 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 ?
I'm not saying otherwise. I'm a bit tired of the subject dominating the front page (and every industry conversation, and the news). Ten years ago, I would have asked with some suspicion "does this relate to blockchain?" Sign of the times. Just as bad as what, personally only being interested in something if it relates to the hot topic of the day? I asked a genuine question, without leaping to any conclusions about the OP. Seems everyone leapt to the conclusion about me which I refrained from.
Well I'm not leaping to conclusions, I'm going on the reason you said you asked.
> Just as bad as what, personally only being interested in something if it relates to the hot topic of the day?
On topics that don't inherently suggest any AI application, asking about AI applications from an AI-cynical perspective is even worse than asking from an AI-hype perspective. They both suck even if they're genuine, and the cynicism pushes it a little bit further.
The cynicism is just asking what the underlying motive is [for the interest in this algorithm]. Whatever metric you're using for judging an honest question as "better" or "worse", you didn't answer the question (someone else did), you misinterpreted it, and you still feel the need to judge its validity. Whatever reasons you have for doing so and then trying to turn it into a morality play or a spectacle, as in, how dare you ask if this relates to back propagation? Oh it's even worse than I thought! - all of that calls your motivation into doubt and brings up a whole galaxy of questions as to why you'd find it necessary to attack someone for asking a plain technical question. None of which I care about kmowing the answers to.
At school they say: There are no stupid questions, only stupid answers. Consider what negative value you have brought to this conversation, without providing any insight whatsoever.
> you didn't answer the question (someone else did), you misinterpreted it
> doing so and then trying to turn it
Do you have me confused with someone else? I did not reply until after you said why you asked. I didn't misinterpret anything.
I'm not trying to do any sneaky redirection. I just think it's bad to bring up AI on non-AI topics!
> At school they say: There are no stupid questions, only stupid answers. Consider what negative value you have brought to this conversation, without providing any insight whatsoever.
You said you dislike the AI dominating the front page, right?
You're contributing to that when you ask questions like the above.
Questions are usually good but sometimes a question is so off-topic that it detracts from the conversation.
