top | item 47112181

(no title)

tromp | 7 days ago

Individual busy beavers BB(n) are finite natural numbers and thus quite computable. A related uncomputable number is the halting probability Omega of a universal prefix machine (whose programs form a prefix free set). By collecting enough halting programs to accumulate a probability of at least the first n bits of Omega (as a binary fraction), you will have determined all programs of length at most n that halt and thus also the busy beavers up to that size.

discuss

order

lich_king|7 days ago

"A real number in which each decimal digit at position n is equal to the first digit of BB(n)."

Since you asserted that individual BB(n) numbers are computable, I think you will have no difficulty writing an algorithm that outputs that.

cofunctor|7 days ago

Such an algorithm would be computing the (uncomputable) function BB : Nat -> Nat, and not the computability of a given BB(n). Every fixed natural number is computable: just print out the number.

This is a subtlety of doing computability theory in classical foundations. It’s akin to how every concrete instance P(x) of a decision problem P is decidable: just use excluded middle to figure out if P(x) is true or false, and then use the Turing machine that immediately accepts or rejects regardless of input. This is very different from writing a machine that has to decide P(x) when given x as an input!

tromp|7 days ago

I did just that for the first 37 BB numbers at https://oeis.org/A333479

I could write a few more given enough time, but writing later ones will take someone more omnipotent than me.

You may be confusing the true statement "for each n, BB(n) is computable" with the false statement "\n -> BB(n) is computable".