logoalt Hacker News

olmo23yesterday at 12:03 PM3 repliesview on HN

You can not rely on brute force alone to compute these numbers. They are uncomputable.


Replies

karmakazeyesterday at 12:16 PM

The busy beaver numbers form an uncomputable sequence.

For BB(5) the proof of its value is an indirect computation. The verification process involved both computation (running many machines) and proofs (showing others run forever or halt earlier). The exhaustiveness of crowdsourced proofs was a tour de force.

arethuzayesterday at 12:07 PM

Isn't it rather that the Busy Beaver function is uncomputable, particular values can be calculated - although anything great than BB(5) is quite a challenge!

https://scottaaronson.blog/?p=8972

show 2 replies
PartiallyTypedyesterday at 12:07 PM

They are at the very boundary of what is computable!