3 ms·

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

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 :)

FartyMcFarter 3y ago
> "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. [1] https://julienmalka.me/collatz.pdf https://julienmalka.me/collatz.pdf
- neilkk 3y ago
  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.
  - FartyMcFarter 3y ago
    > I think the point here is that it was not known whether all 3,3 halting problems are reducible to trivial Collatz-like problems. True, but it still isn't known either way. Nothing changed in that regard.
    - neilkk 3y ago
      'trivial' isn't a mathematical concept. If no one has shown why this problem is trivial, it isn't trivial.
      - FartyMcFarter 3y ago
        This problem isn't trivial, but neither are the ones we could already reduce BB(3, 3) to (via Conway's construction).
        neilkk 3y ago
        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.
      - deleted 3y ago
        [deleted]
- sligocki 3y ago
  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.

FartyMcFarter 3y ago

> "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. [1] https://julienmalka.me/collatz.pdf https://julienmalka.me/collatz.pdf

neilkk 3y ago
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.
- FartyMcFarter 3y ago
  > I think the point here is that it was not known whether all 3,3 halting problems are reducible to trivial Collatz-like problems. True, but it still isn't known either way. Nothing changed in that regard.
  - neilkk 3y ago
    'trivial' isn't a mathematical concept. If no one has shown why this problem is trivial, it isn't trivial.
    - FartyMcFarter 3y ago
      This problem isn't trivial, but neither are the ones we could already reduce BB(3, 3) to (via Conway's construction).
      - neilkk 3y ago
        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.
    - deleted 3y ago
      [deleted]
sligocki 3y ago
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.