top | item 40862860

(no title)

6nf | 1 year 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)?

discuss

order

Sniffnoy|1 year ago

Yeah, that would definitely surprise me.

myrmidon|1 year 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.