3 ms·

> "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 c

> "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.

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.