Hacker News new | past | comments | ask | show | jobs | submit login

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




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: