Hacker News new | ask | show | jobs
by 6nf 709 days ago
> 5 states and 2 symbols is just so few with which to try to encode undecidable behavior.

Would you be brave enough to say the same thing about BB(6) or BB(7)?
1 comments
Sniffnoy 709 days ago
Yeah, that would definitely surprise me.
link
myrmidon 709 days ago
Would you consider the Collatz conjecture as potentially undecidable?

Because that one needs to be solved for BB(6) already: https://wiki.bbchallenge.org/wiki/Antihydra

Considering how we made basically no real progress on it mathematically in a whole generation, solving BB(6) within the next decades would be a miracle, and I would bet a lot against it.

I can't see us EVER getting to BB(10), no matter how advanced humanity grows (and it would be meaninglessly large anyway).

I think 765 is just a huge overestimation based on the fact that it is somewhat straightforward to construct.

link
Sniffnoy 708 days ago
First off, it's not Collatz, it's a Collatz-like problem.

But yes, I'd be very surprised if Collatz were actually undecideable, even if it's well beyond the reach of current mathematics.

I agree with your statements about BB(10) and BB(6), but they just aren't very relevant. I agree those involve extremely difficult problems likely well beyond the reach of current mathematics, but I'd still be very surprised to find anything undecideable in there. There's a big difference between being truly undecideable and merely well beyond the reach of current mathematics!

(Also, the current record for undecideability is 745, or 765.)

link