Comment by FartyMcFarter | Hacker News Reader

Comment by FartyMcFarter | Hacker News Reader

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

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

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?

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

Reply on news.ycombinator.com