Solve the busy beaver

Question

Given a number n, calculates BB(n) (the maximum number of 1s finally on the tape, among all halting 2-symbol n-state Turing machines with tape of zeros).

To solve the problem, you are given an extra (black-box) function H as input, which takes a function in your language (f) and returns a truthy/falsy value indicates whether this function will halt. However, the function f must not have any side-effects (I/O operations, timing, etc.) or call the halting function H.

Note that, there is no restriction on how you use the function H. A possible way is to use the function H to check if each Turing machine halts, and then simulate those to calculate the maximum, but there are other ways to compute BB(n).

You need to prove that it solves such a problem. Shortest code in bytes wins.

Definition of Turing Machine:

Turing machines, each member of which is required to meet the following design specifications:

    The machine has n "operational" states plus a Halt state, where n is a positive integer, and one of the n states is distinguished as the starting state. (Typically, the states are labelled by 1, 2, ..., n, with state 1 as the starting state, or by A, B, C, ..., with state A as the starting state.)
    The machine uses a single two-way infinite (or unbounded) tape.
    The tape alphabet is {0, 1}, with 0 serving as the blank symbol.
    The machine's transition function takes two inputs:

        the current non-Halt state,
        the symbol in the current tape cell,

    and produces three outputs:

        a symbol to write over the symbol in the current tape cell (it may be the same symbol as the symbol overwritten),
        a direction to move (left or right; that is, shift to the tape cell one place to the left or right of the current cell), and
        a state to transition into (which may be the Halt state).

    There are thus (4n + 4)2n n-state Turing machines meeting this definition.
    The transition function may be seen as a finite table of 5-tuples, each of the form
    (current state, current symbol, symbol to write, direction of shift, next state). 

Answer 1

Perl 5, 149 147 bytes (+15 bytes if you want to be really strict)

Generates all Turing machines, use H as oracle to see if they halt and if so runs them, count the number of 1s and take the maximum

#!/usr/bin/perl -p
$"=",",@t=1..$_;map{H($f=sub{my%v;$v{$n}=$1while/(A?)(\d+)(\W)$2$v{$n+=$3.1}/;map/A/,%v})&&\$G[&$f]}glob join"V{,A}{@t,0}{+,-}",0,<{@t}{,A}>;$_=$#G

Slightly breaks the conditions on f though not in an very bad way.

• $n is the starting position on the tape and is a global. So on each new run it starts where the previous Turing machine left off. But since the tape state is local and starts empty it doesn't matter where you start, so it's not actually used to communicate anything (adding $n to the my solves that at a cost of 5 bytes)

• I pass the actual Turing machine in global $_. That's also easily solved by e.g. a for loop over my variable $g and use it in $f via closure with while$g=~/.../ at the cost of 10 bytes. However the current way has the advantage that I can also see $_ inside H and return true for a few halting Turing machines so that I can really compute BB(1) and BB(2) and BB(3) (BB(3) takes 90 minutes on my computer)

Try it online!

The TIO link implements an actual (sort of) halting function in the header.

• The default version has the actual size 1 to 3 busy beaver hard-coded and returns true only for that particular Turing machine. All others return false

• If you add a 1 on the next input line after the size then H will be a real halting function but only for a tape that runs from -10 to 10. It will return false for any Turing machine that repeats its complete state or reaches the edge of the tape (so 19 tape positions can actually be used). It returns true for any Turing machine that halts on this restricted tape. This is enough to really calculate BB(1), BB(2) and BB(3) (you'll need lots of patience and memory for BB(3) but it does work). It also prints out some info about long running machines it finds along the way.

• If instead you add -1 on the next input line after the size then H will behave like what is described for extra argument 1 but will also show the full execution trace of every Turing machine it tries.

Each Turing machines is represented by a strings that describe all input tuples with their corresponding output state. A tape value is either A (for 1) or empty (for 0). The states are numbered from 1 to n, 0 is the halting state. A tuple is the concatenation of:

value to write to tape (A or empty)
new state (1 to n or 0)
direction to move the head (+ or -)
input state (1 to n)
input tape value (A or empty)

The full string consists of a dummy 0 and then 2n tuples in increasing order all separated by V. So for example a 2 state busy beaver Turing machine in this notation is:

0VA2+1VA2-1AVA1-2VA0+2A

which represents these 4 tuples:

A2+1     in state 1 seeing 0, write 1 move right go to state 2
A2-1A    in state 1 seeing 1, write 1 move left  go to state 2
A1-2     in state 2 seeing 0, write 1 move left  go to state 1
A0+2A    in state 2 seeing 1, write 1 move right go to state 0 (halt)