Here’s why I’m interested in “Is the Collatz Conjecture Baker-Hard?”
Tao is basically saying that there’s no way to solve the Collatz Conjecture without creating (or using) Fields-Medal-type math.
In other words, if you were transported to the early 1960s, your resolution of the Collatz Conjecture would incidentally garner you a Fields Medal for establishing that the powers of 2 and 3 grow apart at an exponential rate.
In other words, a math kook isn’t going to solve the Collatz Conjecture without re-developing some very advanced mathematics (or at least knowing about it, and exploiting it).
That’s should be very sobering for a math kook!
At first I thought this was just a feeling that Tao expressed in his blog, but he seems to be saying it’s a provable fact rather than a feeling.
Something akin to, “Don’t work on a polynomial algorithm for solving the Traveling Salesperson problem optimally, because it’s NP-complete. Unless you’re prepared to solve P vs NP (as a side effect!), don’t work on that.”
We used to call a lot of problems “AI hard”. I worked on one of them for many years. Machine translation was called “AI hard” because you could always make up a translation problem that the machine would get wrong unless it knew a particular fact about the world. That didn’t bother us, because we were trying to solve it at 90% (like building a useful, suboptimal Traveling Salesperson algorithm). But what do you know, folks first demonstrated the power of neural sequence modeling on machine translation, then used those techniques to build ChatGPT.
Ok, long preamble to the next post, trying to make technical sense of Tao’s assertion.