13 ms·
Terence Tao Proves Result on the Collatz Conjecture
- vecter 7y agoOne of the aspects of math that I find beautiful is the deep connection between often seemingly unrelated topics. Connecting PDEs, which is a branch of analysis and what I consider "continuous" mathematics to something that seems to me like a discrete number theory problem is beautiful. The bit of intuition for why this might be the case in the article is nice: > With a PDE, you plug in some values, get other values out, and repeat the process — all to understand that future state of the system. For any given PDE, mathematicians want to know if some starting values eventually lead to infinite values as an output or whether an equation always yields finite values, regardless of the values you start with. > For Tao, this goal had the same flavor as investigating whether you always eventually get the same number (1) from the Collatz process no matter what number you feed in. As a result, he recognized that techniques for studying PDEs could apply to the Collatz conjecture.
- oefrha 7y agoThe connection is actually very well known. See https://en.wikipedia.org/wiki/Dynamical_system https://en.wikipedia.org/wiki/Dynamical_system.
- vecter 7y agoI don't doubt that. I'm not a mathematician, just a guy who took some classes in college. For a noob like me, this is all cool to see for the first time.
- xdavidliu 7y agoI don't actually think it is that well-known, you were completely right to point out. Also, I suspect the "dynamical systems" wikipedia page is completely irrelevant.
- oefrha 7y agoThe Collatz map defines a discrete dynamical system on N^+. I don't know about your background, but the connection isn't hard to see for anyone with a tangentially related background. I have studied https://en.wikipedia.org/wiki/Arithmetic_dynamics https://en.wikipedia.org/wiki/Arithmetic_dynamics (that page does mention Collatz incidentally) myself in a past research project, so the connection is known to me. The dynamical systems Wikipedia page serves as an entry point to the broad topic, but it's a huge field and intersects with many others so apparently a single short page isn't gonna cover everything. What I meant was that "Collatz's got something in common with PDEs" isn't the unique insight of Terence. Of course the connection isn't obvious to, say, the average coder, but it's universally known among mathematicians who have at least studied related fields for a little bit. Terence's magic is on a much higher level.
- xdavidliu 7y agoI did my PhD in theoretical physics, and part of my thesis was on nonlinear eigenvalue problems in PDEs. I wasn't aware of the connection; though I guess it really depends on what you mean by "it's well known".
- xdavidliu 7y agowhere on that page does it discuss the connection?
- emmelaich 7y agoMy favourite story on this is Feynman's use of PDEs in the Connection Machine design. http://longnow.org/essays/richard-feynman-connection-machine/ http://longnow.org/essays/richard-feynman-connection-machine...
- BlueTemplar 7y agoThank you so much for sharing this!
- edflsafoiewq 7y agoI've always wanted to see his analysis of the behaviour of the router in terms of PDEs.
- core-questions 7y agoI really want to buy the CM-1 T-Shirt, but with duty and shipping it's too much for a shirt the comments describe as being of poor t-shirt quality.... http://www.tamikothiel.com/cm/cm-tshirt.html http://www.tamikothiel.com/cm/cm-tshirt.html https://shop.spreadshirt.com/mission-base-creations/cm+1+logo+flexprint?idea=5d89c895f937647d81fe06aa https://shop.spreadshirt.com/mission-base-creations/cm+1+log...
- knzhou 7y agoNow that was a great example of an accessible, technically and culturally accurate article. For stuff like this, Quanta magazine is generally the world leader.
- prox 7y agoWas thinking the same thing! A catchy title that actually described the content.
- gdy 7y agoWhat does "culturally accurate' mean?
- OJFord 7y agoI assume that the characterisation of the problem as 'dangerous', 'alluring', tempting', etc. to mathematicians is accurate.
- rsj_hn 7y agomeh. No, I think this is the sensationalization we expect from pop-sci accounts.
- new2628 7y agoI guess they mean it accurately captures the "mathematical culture" surrounding this problem, which I can confirm.
- madez 7y agoI understand it as that people with expert knowledge from the field, mathematicians in this case, agree with the classification of the problem on a social and cultural level.
- ptah 7y ago> Then this past August an anonymous reader left a comment on Tao’s blog. The commenter suggested trying to solve the Collatz conjecture for “almost all” numbers, rather than trying to solve it completely. maybe a time traveller nudging a result that will be significant for humanity's future?
- kachnuv_ocasek 7y agoHad the same thoughts. This is also not the first time that some comment on Terry Tao's blog nudged him or his research.
- Grue3 7y agoWell, studying a conjecture for "almost all" numbers doesn't actually prove anything about the conjecture because just a single exception would disprove it. There are a few conjectures that had particularly large exceptions [1]. It's possible that Collatz exception will be so large that it's effectively uncomputable or it's existence is unprovable in ZFC [2]. Somebody probably tried it, but I wonder if describing particularly long sequences where r_(n+1) = 3*r_n+1 is always odd would help. There are results for arbitrarily large arithmetic progressions having some specific property [3], so there's no reason why other progressions couldn't be studied in that way. [1] https://en.wikipedia.org/wiki/P%C3%B3lya_conjecture https://en.wikipedia.org/wiki/P%C3%B3lya_conjecture [2] https://en.wikipedia.org/wiki/Zero_sharp https://en.wikipedia.org/wiki/Zero_sharp [3] https://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem https://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem
- jeromebaek 7y agoAlso known as hailstone problem from GEB
- aroberge 7y agoThe Collatz conjecture predates GEB by many years. Renaming it to something else by the author of GEB was a way to misappropriate someone else's work.
- stan_rogers 7y agoUm, no. Collatz's conjecture was that the sequence will always reach one, and that conjecture was entirely avoided in GEB. Any number that would result in the 1-4-2-1 closed loop was referred to as "a wondrous number" in the GEB dialogs, and the concentration was on the idea that while you could test any number for the property of wondrousness, nobody knew how to prove that any given number would be wondrous without testing it. It was used as a soft introduction to the halting problem.
- huhtenberg 7y agoI'm pretty sure the "halistorm numbers" term also predates GEB.
- scarejunba 7y agoThat video at the top is very neat. Was it manually made or is there software that makes it easy to do? Also which is the comment they're talking about? I can't seem to find an anonymous one talking about this on the original post https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/ https://terrytao.wordpress.com/2011/08/25/the-collatz-conjec...
- hcs 7y agoI suspect it was this one? https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/#comment-84973 https://terrytao.wordpress.com/2011/08/25/the-collatz-conjec...
- oefrha 7y agoProbably made with d3.js. https://d3js.org/ https://d3js.org/
- acqq 7y ago> That video at the top is very neat. It doesn't contain number 9, so I somehow miss what it was supposed to demonstrate.
- _Microft 7y agoThe animation is a bit strange. I think it's meant to show which numbers will eventually end the cycle at 1. Having the numbers appear in the reverse order compared to what the rules are does not help, in my opinion. Take 16 and 5. While 16 is shown first and 5 after, the meaning is actually that you can get from 5 to 16 by applying the odd rule (3*x+1) and from 10 to 5 by applying the even rule (x/2).
- cyborgx7 7y agoOh, I see. It's about creating the set of numbers that do end up at 1 by starting at 1 and applying the operations in reverse order. That is neat. They should have explained that in the article.
- oefrha 7y agoTechnical post from Terence Tao: https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/ https://terrytao.wordpress.com/2019/09/10/almost-all-collatz... The paper: https://arxiv.org/pdf/1909.03562.pdf https://arxiv.org/pdf/1909.03562.pdf
- hiruxxy 7y agohttps://www.helathlktip.club/2019/12/how-to-weight-loss.html?m=1 https://www.helathlktip.club/2019/12/how-to-weight-loss.html...
- huffmsa 7y agoThe question as I, not a mathematician, read it is > For a given number, can using the operations 3n+1 and n/2 make it converge to a value of 2^i Because that's what you need. If you can get on the 2^i branch, you've won.
- ReptileMan 7y agoNot a mathematician but that is too close to mesenne primes to make a quite fun possible connection. Since messene you have points that 3n cannot hit.
- huffmsa 7y agoBut it's 3n+1, so you're always getting an even number 50% of the time. And for every number you hit along the way, assuming you make it down to 1, you can stop your iteration if you've previously seen the number
- thaumasiotes 7y ago> And for every number you hit along the way, assuming you make it down to 1, you can stop your iteration if you've previously seen the number You can stop your iteration if you come to a previously encountered value, because the (n+1)th number in the sequence is strictly a function of the nth number. Assuming that you make it down to 1 gives you nothing. The whole point is to prove that you always make it to 1, or -- equivalently -- to show that you can never reach a previously encountered number without first reaching 1.
- huffmsa 7y agoBut you'll always reach a previously seen number because 3n+1 will never be a prime number.
- thaumasiotes 7y agoI can see that 3n+1 is never prime. Why does that guarantee that you will always reach a previously seen number?
- cyborgx7 7y agoI can totally see how one could be sucked into this problem. The solution seems immediately reachable. After giving it some thought, I can prove that it is equivalent to "every number will at some point reach a power of 2" because from a power of two you then go straight to 1 through divisions. This result seems even more reachable since I no longer need to prove that numbers eventually get smaller. I'm sure this is not a new discovery to people who have worked on the problem. But part of me really wants to spend the rest of the day puzzling around with where that approach goes. Edit: Thought about it more. The two ways it doesn't hit 1 would be for it to find a loop, that never hits a power of 2 or to grow infinitely. Thinking about how a loop with 3n+1 and n/2 would have to function, I think it's probably pretty easy to prove that 4-2-1 is the only loop that is possible. That leaves us with the infinite grows, but without ever hitting a power of 2. Edit2: Turns out 4-2-1 being the only loop that is possible is actually not easy to prove at all and isn't proven. But no matter, that wasn't how I was going to continue working on the problem anyway. The most promising solution to me is an inductive proof. Since I know all powers of 2 converge to 1 and only have /2 applied to them, my next step is to find the properties of numbers n such that 3n+1 is a power of 2. Only for every second power of 2 is this a whole number. The numbers for the powers of 2: [4, 16, 64, 256, 1024] have the possible precedents: [1, 5, 21, 85, 341]. Interestingly every subsequent number can be built from the previous one by 4n+1. Clearly it's 4 because it's every second power of 2. I feel like, if you recognize the structure of every number in the tree, you can prove that every natural number has one of those structures. And then you are done. Once again, I'm completely aware none of this is original thought. But I enjoy it anyway. Edit3: Every even number will be divided by 2 until it is an odd number. Now we only have to look at the structure of the odd numbers.
- huffmsa 7y agoHad the same thought further down the comments. Since you're getting even numbers at least 50% of the time, eventually you should go on a run. You also benefit from hitting a y =2^n x N number because you get to greatly reduced the size of y Further, every time you make it down to 1, you can append the values you hit on your way down to a list of seen values, as they're part of a convergence chain, meaning if you see them in a future cycle, you can stop your iteration early because you have a known outcome. So this doesn't necessarily become a computationally heavy problem with large numbers.
- wil93 7y ago> Tao used this weighting technique to prove that almost all Collatz starting values — 99% or more — eventually reach a value that is quite close to 1. This allowed him to draw conclusions along the lines of 99% of starting values greater than 1 quadrillion eventually reach a value below 200. Isn't this equivalent to saying that "99% of starting values greater than 1 quadrillion eventually reach 1"? I mean, once you reach a value below 200 then you will continue and reach 1. Not only below 200, but below any limit that was experimentally verified (i.e. around 10^20)
- MichaelBurge 7y agoIf you choose giant starting numbers(like "Tree(3)"), then maybe "quite close" is 10^100.
- tel 7y agoSpeculation only, but the method of proof might, in its key step, only bound to ~200. This is a more meaningful result to present if your reader knows that 200 is a as good as 1 because it loses nothing and also highlights something about the bound produced.
- Sharlin 7y agoYes, I believe the key phrase was ”along the lines of” and Tao’s result doesn’t actually prove any particular constant bound which would indeed be a much stronger result.
- egdod 7y agoFrom Tao’s blog post, it sounds like the result is more in terms of things like: for almost all n<N, the maximum value of n’s Collatz orbit is bounded by extremely slow-growing functions of N (e.g. log log log log N).
- AstralStorm 7y agoNice. This means that any resulting limit cycle will be tiny, thus hard to hit. So he actually proved that it's hard to disprove the conjecture.
- pg_bot 7y agoI got sucked into this problem as an undergraduate in mathematics. I similarly wanted to limit my search space and my initial work lead me down the path of prime factorization. If every prime number follows this pattern then logically every number also follows this pattern. Then you get to the hard part which is why or why not would a prime number follow this pattern. So then you go looking for the reasons why prime cycles can or cannot exist, your brain melts, and then you work on something else. Fun times though.
- cyborgx7 7y agoAs a computer science (Informatics) student, I shy away from any path in a prove that makes me make some kind of statement about primes. They are the death of every approach they are involved in, to me. From my one hour of thinking about this problem, I think sums of finite sequences are a much more promising approach. But obviously you'd know way more about all of this than me.
- RockIslandLine 7y agoSieve of Aristothenes + induction seem most likely to me. "For every binary sequence of length X, the Collatz iteration ends at 1. Adding more zeros clearly does not change the result, therefor adding more ones is the only path which might disprove the conjecture." Eventually you build up to a catalog of proven sequences that all other numbers must necessarily step into at some point.
- AstralStorm 7y agoYou just made it as hard as proving generalized Riemann hypothesis. Not good progress with that task. Might as well start working on Goldbach conjecture.
- mkl 7y ago*Eratosthenes, best known for being the first person to calculate the circumference of the Earth.
- 7y ago
- nickcw 7y agoA few years ago I got interested enough in this that I bought the book mentioned in the article "The Ultimate Challenge: The 3x + 1 Problem." If you want to see dead ends other people have gone down and read some actual results and learn some history it is a good read for the mathematically inclined. Some of the maths went over my head but I enjoyed it!
- dmayle 7y agoI must admit to being curious about this book. I don't see how this hasn't been proven already (though I can't write mathematical proofs myself) If you look at this as a series of consecutive operations, every odd operation grows by a little over three, and is guaranteed to be followed by an even operation. Even operations shrink by a little more than three, so all that's required is to compare the cardinality of those two offsets to see whether continued operations are growing or shrinking. In the case of odd operations, as the infinite series of operations continues, the offset gets smaller and smaller. In contrast, the size of the offset for even operations doesn't change as the series of operations continues, which should mean that numbers shrink more than the grow, just ever so slightly. (To understand the even operations, you have to look at expected values. 1/2 of all even operations will produce an odd operation after dividing by two, 1/4 after dividing by four, 1/8 after dividing by eight. The infinite sum (1/2)^2n converges to 1/3, with an actual value of 1/3 - (1/3)*(1/2)^2n.
- Akababa 7y agoThere are some good ideas in there, but I can see a few problems with this proof: 1. It doesn't show the result for all natural numbers, only some "high probability" fraction of them (similar to what Tao did). 2. The expected value of the ratio being 1 doesn't imply that the actual number goes to 1, since it could be stuck in an endless loop with itself as the minimum. 3. 3n+1 doesn't necessarily have a uniform distribution over the even numbers. Tao gets around this by picking some "stable" subset of numbers that don't move too much under the transformation.
- rmidthun 7y agoBy using expected value, you are assuming that the distribution of the even numbers is uniform. You will need to prove that first, and I suspect that will be difficult.
- dclowd9901 7y agoWhat would it mean if they found a number — one number — that didn’t adhere to this rule?
- JoeAltmaier 7y agoOf course that's one way of proving this wrong. But you have to start above 18 quadrillion. Because all the numbers less than that have been tried.
- 3pt14159 7y agoHas anyone tried really, really large numbers picked at random?
- JoeAltmaier 7y agoOne approach. But I'd suggest it has less than a one-in-18-quadrillion chance of working. From the statistics so far.
- gnode 7y agoIt's trivial to do. Here: https://js.do/code/383036 https://js.do/code/383036
- bluGill 7y agoYou cannot find ONE such number. Either there is a loop that doesn't include 1, so you found a sequence of them. The other possibility if the sequence goes to infinity and so you found and infinite number of counter examples.
- mensetmanusman 7y agoHow would you calculate the number sequence out to infinity?
- dclowd9901 7y agoI guess my question was more “what could that mean?”
- thetanil 7y agoany even number can be divided by 2 until it reaches 1. any odd number ends in 1,3,5,7,9. Any of those numbers multiplied by 3 and added to 1 ends in an even number. I don't get why this is hard?
- JoeAltmaier 7y ago18
- chki 7y ago>any even number can be divided by 2 until it reaches 1. What do you mean by that?
- brokensegue 7y agoThey thought all even numbers are powers 2
- bhaak 7y ago> any even number can be divided by 2 until it reaches 1. 6 wants to have a word with you.
- thetanil 7y agothank you
- justincredible 7y agoThe least counterexample, nice.
- deleted 7y ago[deleted]
- cyborgx7 7y ago>any even number can be divided by 2 until it reaches 1. It's hard because this is wrong. 18 is an even number. 18/2 is 9. 9 can no longer be divided by 2 and is not one.
- idclip 7y agoI want to know who made that comment, what a unit.
- paulpauper 7y agothe proof if it exists will involve math is the very complicated and abstract and cutting-edge, similar to the proof of Fermat's Last Thereon . It will involve some sort of result, I am guessing, from complex analysis an number theory and then generalized in such a way as to prove this result.
- AstralStorm 7y agoI suspect that about the only other class of numbers that could loop starts from a prime. (Because otherwise after a series of steps you could essentially run the procedure in parallel.) So you would have to find a specific class of prime numbers. This is darn hard to find ever.
- johnrob 7y ago1 is the only number for which 3n + 1 = 4n. So a number that didn’t reduce to 1 would have to get stuck in a loop of multiple repeated values. That seems unlikely.
- wyatt777 7y agoApproximating almost up-to, is not rigorous proof in math, but looking forward to positive conjectures.
- tester89 7y ago> In the 1970s, mathematicians showed that almost all Collatz sequences — the list of numbers you get as you repeat the process — eventually reach a number that’s smaller than where you started I don’t understand why this doesn’t prove the conjecture. Like if you start with x, and you reach y: y < x, then couldn’t one reäpply the quoted statement to show there exists z: z < y < x and wouldn’t iterating of this statement eventually lead to 1 < … z < y < x
- odyssey7 7y agoHuh, neat. I just read about this after seeing it as an example in UPenn's CS 194 "Introduction to Haskell" notes. hailstone :: Integer -> Integer hailstone n | n `mod` 2 == 0 = n `div` 2 | otherwise = 3*n + 1 https://www.seas.upenn.edu/~cis194/spring13/lectures/01-intro.html https://www.seas.upenn.edu/~cis194/spring13/lectures/01-intr...
- errantspark 7y agoit really is fantastic how simple it is to express, i sketched in the console as i was reading the article n=>n-1?n%2?c(n/2):c(n*3+1):1
- bjoli 7y agoNow see how fast you can make it run! 22 year old me was the king of the project Euler forum for that specific problem ("find the longest sequence below 1000000") until my post got removed (which all newer posts for old problems are). Doing those stupid things actually made me learn a lot about how computers work
- jboggan 7y agoThis was the problem that turned me from a music major to a math major and eventually led me down the path to computer science. It's a beautiful and cold problem and I love to see any progress made on it.
- archi42 7y agoMy initial idea is to go the other way around: We can count natural numbers using the successor function, starting at 1. E.g.: 1, s(1) = 2, s(s(1)) = s(2) = 3, and so on. So if we see a number n, we know it's s(n-1), which is s(s(n-2)) and so on, until we reach 1. So we have a nice, linear chain, and it's trivial to construct an algorithm f(n) [or more mathematically, a function f: N -> {s,ss,sss,...}] that (i) produces the necessary operations to reach any given natural number n in that chain, starting at 1, and (ii) terminates for every input n. Now we don't use s(x), but instead two operations that are inverse to the Collatz rules: a(x) = 2*x and b(x) = (x - 1)/3 (with b of course is not always being possible). Starting at 1, this can now be used to construct a tree containing "some" numbers, and we can use that it to describe a path to a number from the root. If the conjecture holds, the tree constructed from these functions has to contain all natural numbers. My nudge is then: If I have a number n, can I give an algorithm/function f': N -> {a,b,aa,ab,ba,bb,...} that (i) finds a path to n, and (ii) always terminates? Answer: I have no idea =) E.g.: f'(5) = aaaab <=> b(a(a(a(a(1))))). So we have f'(1)=no idea how to represent, f'(2)=a, f'(3)=aaaabab, f'(4)=aa, f'(5)=aaaab, f'(6)=aaaababa, f'(7)=aaaabaaab[...], f'(8)=aaa,... (However, maybe it is not possible to even construct f': I believe the target space of f is of another infinity than the target space of f' -- obviously this isn't my area of expertise).
- jcranmer 7y agoThe algorithm is easy: enumerate all possible strings in increasing order of length, and return the first string you found that returns n. If there is such a string for n, then this will find it. It will terminate if and only if there is such a string for every integer (i.e., the Collatz conjecture).
- archi42 7y agoIf it only was that simple :) since we can not solve the halting problem, pure breadth first search doesn't help. We need to find another algorithm that makes use of the tree's structure. If bfsearch could be proven to be the best algorithm, this would reduce the conjecture to the halting problem.
- btilly 7y agoSee https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/ https://terrytao.wordpress.com/2019/09/10/almost-all-collatz... for a more detailed explanation. His actual result is this. Suppose that f(N) is a function from the natural numbers to the reals that has infinity as a limit. Let X be the set of natural numbers who eventually go below f(N). Then the logarithmic density of X is 1. Here logarithmic density is the limit of the following ratio: sum(1/n for n in X and < N) / sum(1/n for n < N) Now you just have to pick f that grows very, very slowly. For example f(N) = log(log(log(x)))).
- SubiculumCode 7y agoI know this is a fluff comment and meta, but I know many of us came here from /. years ago. This article was put on /. and comparing the comments of /. and HN on this article really highlights how far /. has fallen.
- gefh 7y agoIs slashdot full of people who think they can solve it in the comment thread?
- SubiculumCode 7y agoNo it is filled with people who think that the mathematician should do something more useful with their time, like make targeted ad algorithms, or something.
- RcouF1uZ4gsC 7y ago> The Collatz conjecture is quite possibly the simplest unsolved problem in mathematics — which is exactly what makes it so treacherously alluring. IMO that distinction actually belongs to Goldbach's conjecture which is: Every even integer greater than 2 can be expressed as the sum of two primes.
- tlholaday 7y agoIs it your opinion that understanding the meaning of "two primes" is simpler than understanding the meaning of even, odd, tripling, halving, and adding on3?
- Taek 7y agoIn my opinion it's not simpler, primes are a difficult concept. Tripling and halving is simpler.
- TrainedMonkey 7y agoWhat tripped me up for a second is that primes don't have to be distinct. So 4 is sum of 2 + 2 and 6 is sum of 3 + 3.
- edanm 7y agoI think Goldbach is easier for people who know a bit about math (i.e., remember the definition of a prime number.) Collatz is easier to explain for someone with no background.
- jlarocco 7y agoIt's an interesting puzzle, but is there any significance to it? Are there an infinite number of sequences like this, but with different numbers or different operations? Is there any value proving things about them? Seems like a shot in the dark looking at an arbitrary sequence and proving things about it.
- aerovistae 7y agoI feel like you've asked this in an unnecessarily adversarial tone, but the question is a great one whose answer is valuable for understanding this type of thing. I don't know what the answer is, I'm just saying it's a good question.
- baq 7y agoIt isn’t about the result, it’s about the tools that have to be discovered to get that result. It’s likely there’s an as yet unknown branch of number theory required or perhaps a hidden link to something apparently unrelated.
- jorgenveisdal 7y agoTao will be remembered 500 years from now.
- devit 7y agoIt's interesting that it seems that some very short propositions require very long proofs. Are there any results on the length (or maybe Kolmogorov complexity) of the shortest proof for provable propositions of length N? (in a specific logic system, I suppose) I.e. how hard to prove is the hardest proposition of length of N and how does it grow with N? how about the average random provable proposition?
- bentona 7y agoIt is hilarious to me that the thread about this "Dangerous" problem is full of approaches to solving it :)
- atemerev 7y agoI have a stupid question. If binary representations of numbers in the hailstone sequence for Collatz conjecture can be written as a 2-tag system (a → bc, b → a, c → aaa), and m-tag systems are Turing complete for m>1, and Collatz conjecture is a sort of halting problem in this framework (there is a halting criteria), and "deciding whether a particular algorithm for Turing machine will/won't halt on every input" is a totality problem, which is also undecidable — can a proof of undecidability of Collatz conjecture be approached this way? What is the major problem with this line of thought?
- inimino 7y agoIf I understand your comment correctly, "deciding whether a particular algorithm ..." means an arbitrary algorithm. For a specific algorithm, of course sometimes it is possible to prove that it halts for every input. It's only undecidable if the algorithm is regarded as an input.
- deleted 7y ago[deleted]
- oneepic 7y agoJust reading the summary of Collatz reminds me a whole lot of the Josephus problem. 3x+1 is a similar expression you'd see when you're trying to enumerate indices in that problem. Dividing by two is similar to going once around the circle killing every other index. I wonder if that's been explored?
- sidcool 7y agoThe title seems to have been changed. Did he prove it for good or for most of the values?
- FrozenVoid 7y agoWhat don't they instead work from the opposite direction: Create an abstract model of a Collatz loop that doesn't end with 1(instead looping back to same number) and prove it can't exist(Reductio ad absurdum).
- cevi 7y agoThis approach has been explored. It has only been helpful for showing that certain types of (short-ish) cycles can't occur [1]. Showing that the sequence can't get larger and larger forever (without repeating) with this approach has been a non-starter. [1] See https://en.wikipedia.org/wiki/Collatz_conjecture#Cycle_length https://en.wikipedia.org/wiki/Collatz_conjecture#Cycle_lengt... for a few references. The most recent appears to be the paper "Theoretical and computational bounds for m-cycles of the 3n + 1 problem" by Simons and de Weger.