logoalt Hacker News

arethuzayesterday at 12:07 PM2 repliesview on HN

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


Replies

CaptainNegativeyesterday at 1:04 PM

Only finitely many values of BB can be mathematically determined. Once your Turing Machines become expressive enough to encode your (presumably consistent) proof system, they can begin encoding nonsense of the form "I will halt only after I manage to derive a proof that I won't ever halt", which means that their halting status (and the corresponding Busy Beaver value) fundamentally cannot be proven.

show 2 replies
IsTomyesterday at 12:11 PM

> particular values can be calculated

You need proofs of nontermination for machines that don't halt. This isn't possible to bruteforce.

show 2 replies