4 ms·
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 speci
by 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 agoAre 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]