Busy beaver in a coin

Question

\$BB\$ is the busy beaver function, an uncomputable function. Write a program which when given an integer \$n\$ as input, will output \$BB(n)\$, with at least \$\frac 2 3\$ probability. You can do whatever (return something wrong, infinite loop, explode, etc.) in other cases.

To help you compute it, you're given a function that randomly returns 0 or 1 (false or true, etc.). You can decide the exact probability that it returns 0, but all returns of calls should be independent.

Shortest code wins.

Notes

• The exact definition of BB doesn't matter much so not clearly defined above.
• If you encode some code into the randomness, they add nothing to length of your solution(actually it's hard to define code and data here). You should, when constructing the coin, show the code, though.

Answer 1

Python 3.8 (pre-release), 68 66 bytes

lambda x:eval(sum(r()for _ in"X"*4**900).to_bytes(225,"big")[:99])

Try it online!

-2 bytes thanks to @l4m2

r is the random function. Its probability of outputting one encodes a 99-byte code snippet, which is evaluated. This code snippet can then read much more data from the randomness, and basically you can encode any program you want into the randomness stream.

Here is a practical demonstration

Example (less than) 99-byte snippet:

eval((sum(r()for _ in"X"*2**88001)>>80000).to_bytes(1000,"big")[99:])

As you can see, there is no limit to what kind of code we can run

To actually solve the busy beaver problem, the rest of the randomness is dedicated to just storing the answers to the question (that is, the busy beaver numbers).

The probability of failure depends on the first calculation. I think it succeeds with more than 2/3 probability, but i could be wrong. I'll check and add a proof later. Nevertheless, if it fails the criteria, this only results in some adjusting to the magic constants.

For the encoding of the busy beaver numbers, we first use the following encoding (I'm using a list of primes as an example)

[2,3,5,7,...]

Is converted into

110111011111011111110...

Finally, in order to account for the table-maker's dilemma, we replace1 with 10 and 0 with 01, resulting in 101001101010011010101010011010101010101001...

Then we execute the following code:

def get_raw_bit(p):
 # A lot of tries
 tries = 2**(2**p)
 hits = sum(r() for _ in range(2**tries))
 hits >> (tries - p)
def get_bit(p):
 code_len = 1000
 get_bit(code_len + 2*p)
pos = 0
p = -1
while pos < x:
 count = 0
 while get_bit(p:=p + 1):
  count+= 1
print(count)