4 ms·

> Therefore, solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem I don't understand why this is surprising, in fact it seems

> Therefore, solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem I don't understand why this is surprising, in fact it seems trivially provable. Aren't all BB(x, y) problems reducible to Collatz-like problems? BB(x, y) problems are trivially converted to the halting problem: - find all machines with x states and y symbols that halt, set all the non-halting ones aside. - run all the halting machines together one step at a time until they've all halted. The number of steps you've executed is the value of BB(x, y). I believe Conway presented a reduction from the halting problem to collatz-like problems, so finding BB(x, y) for any value of x and y can be reduced to a collatz-like problem with this two step reduction (BB to halting problem to Collatz problem).

deleted 3y ago
[deleted]
dchftcs 3y ago
I think you got the direction reversed. Here you have a reduction of B(x,y) to the halting problem, which only shows that (a subset of) halting is at least as hard as B(x,y). You need a reduction from collatz to halting to B(x,y) instead. Collatz to halting is trivial, halting to B(x,y) seems a bit less so - you need to precisely define which subset of halting problems can be reduced from Collatz yet is no harder than B(3,3).
- deleted 3y ago
  [deleted]
- FartyMcFarter 3y ago
  My understanding is that this blog post converts a specific instance of the halting problem into a Collatz-like problem. It starts with a description of a specific Turing machine, and presents a Collatz-like problem that, if solved, also answers whether that Turing machine halts or not. Isn't this almost exactly what Conway did, with the only difference being that Conway's proof works for all Turing machines, and this proof only works for a specific Turing machine?
  - konstantinua00 3y ago
    Are you talking about FRACTRAN? Halting problem being reduced to [subset of collatz-like problems] says nothing about uncomputability of [all the rest of collatz-like problems] and even less about [does single specific collatz-like problem halt] The only consquence is that "most general" definition of collatz-like problem as a whole is uncomputable
    - deleted 3y ago
      [deleted]

deleted 3y ago

[deleted]

dchftcs 3y ago

I think you got the direction reversed. Here you have a reduction of B(x,y) to the halting problem, which only shows that (a subset of) halting is at least as hard as B(x,y). You need a reduction from collatz to halting to B(x,y) instead. Collatz to halting is trivial, halting to B(x,y) seems a bit less so - you need to precisely define which subset of halting problems can be reduced from Collatz yet is no harder than B(3,3).

deleted 3y ago
[deleted]
FartyMcFarter 3y ago
My understanding is that this blog post converts a specific instance of the halting problem into a Collatz-like problem. It starts with a description of a specific Turing machine, and presents a Collatz-like problem that, if solved, also answers whether that Turing machine halts or not. Isn't this almost exactly what Conway did, with the only difference being that Conway's proof works for all Turing machines, and this proof only works for a specific Turing machine?
- konstantinua00 3y ago
  Are you talking about FRACTRAN? Halting problem being reduced to [subset of collatz-like problems] says nothing about uncomputability of [all the rest of collatz-like problems] and even less about [does single specific collatz-like problem halt] The only consquence is that "most general" definition of collatz-like problem as a whole is uncomputable
  - deleted 3y ago
    [deleted]