Probably more accurate to say that BB(3, 3) looks hard; that is, it encodes a Collatz-type problem, and many Collatz-type problems are very hard to solve (including, of course, the classic Collatz conjecture).
However, this instance might not necessarily be hard. For one, the behaviour seems to be heavily biased; for another, we only have to consider a single trajectory instead of the trajectories for all integers (as with the classic Collatz problem).
Yeah, I've oversimplified a bit with this title. The more accurate statement is in the first paragraph of the article: "Solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem."
I also agree somewhat on the one trajectory vs. multiple trajectories point. However, note that (assuming we live in the world where this TM never halts) proving a single trajectory in this system is "harder" than a single trajectory in the classic Collatz conjecture. Specifically, (assuming the Collatz conjecture is true) proving any single trajectory is "simply" a finite computation. However, proving a single trajectory from the article requires showing that it never halts which will require some more fancy math!
Anywho, I don't want to oversell it. This does not prove that BB(3, 3) requires proving the Collatz conjecture or any existing well-studied open problem in Math. But I think it's sort of a "second best" result: As hard a problem akin to a well studied problem.
How hard is this Collatz-like problem? Well, let's see if anyone can solve it :)
> "Solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem."
> How hard is this Collatz-like problem? Well, let's see if anyone can solve it :)
I thought John Conway already proved that all instances of the halting problem can be converted to a Collatz-like problem [1]. So one could say this about all BB values, not just BB(3, 3). Some will be easy, some will be hard, but all are reducible to Collatz-like problems IIUC.
You are right that every TM can be converted into a Collatz-like problem using Conway's Fractran compilation. So technically the statement "Solving the BB(n, k) problem is at least as hard as solving a Collatz-like problem." is true in general.
However, the Collatz-like problems you will get from this completion will be gigantic, they will not have distilled the problem into a similar description of it's behavior, but instead created a more complicated way of observing that behavior. The Collatz-like problem I present here is a simplification of the behavior of this TM. If you observe the machine running you will see that it is effectively completing these transitions.
In other words, I am not arbitrarily choosing to convert this to a Collatz-like problem simply because it is possible. I am looking at the behavior of this machine and that behavior turns out to be Collatz-like naturally.
Of course none of this proves that my Collatz-like problem really is hard ... but as someone else here mentioned, being hard is not a mathematical thing, it is a belief we have about certain problems we cannot solve after considerable effort.
I think the point here is that it was not known whether all 3,3 halting problems are reducible to trivial Collatz-like problems. Unless someone is able to observe that sligicko's is actually trivial, then this provides a counterexample.
Some reductions via Conway's method give non-trivial Collatz problems even though other simple techniques show the halting question for those machines to be trivial; the Conway reduction sometimes reduces trivial Turing machines to non-trivial Collatz problems.
However, this instance might not necessarily be hard. For one, the behaviour seems to be heavily biased; for another, we only have to consider a single trajectory instead of the trajectories for all integers (as with the classic Collatz problem).