New

The latest blog posts to take off on Hacker News. 3,824 posts.

Any topic
2023
729

BB(3, 3) is Hard

I’m excited to share a 3 state, 3 symbol Turing Machine that cannot be proven to halt or not (when starting on a blank tape) without solving a Collatz-like problem. Therefore, solving the \(BB(3, 3)\) problem is at least as hard as solving this Collatz-like problem, a class of problem for which Paul Erdős famously…