As of the proof of the value of BB(5), there are three candidates for the next Busy Beaver value (and corresponding machine) to find:
BB(6), aka BB(6,2) is the 6-state 2-symbol machine.
BB(3,3) is the 3-state 3-symbol machine.
BB(2,5) is the 2-state 5-symbol machine.
Any proof of the machine for more states or symbols would imply a proof for one or more of the above problems sizes. If multiple problem sizes are proven simultaneously, those options will resolve in equal proportion.
For this question all that is required is a proof as to which machine achieves the BB(x,y) bound in question. An exact value for S(x,y) or Σ(x,y) is not required. An explicit machine is required, along with a proof that it halts and a proof that no other longer-running machine halts. See also /EvanDaniel/will-the-bb6-machine-be-known-by-20 , which uses the same criteria.
A formal announcement by the bbchallenge.org site, peer reviewed papers, or statements by prominent computational complexity experts will be required to resolve this question.
1,000
3.00Reposted from the earlier market which got N/A'd.
Some quick calculations: There are (2*y*(x + 1))^(x*y) Turing machines with x states and y symbols. This means:
6 states and 2 symbols: (2*2*(6 + 1))^(6*2) ~ 2.322e17 (or 232 quadrillion) machines
3 states and 3 symbols: (2*3*(3 + 1))^(3*3) ~ 2.642e12 (or 2.642 trillion) machines
2 states and 5 symbols: (2*5*(2 + 1))^(2*5) = 5.9049e14 (or 590.49 trillion) machines
So just in terms of the number of machines, the order of difficulty should be BB(3, 3), then BB(2, 5), then BB(6, 2). But of course there are clever ways to cut down on the number of machines that one needs to simulate (though many of them do only apply to the 2-symbol case), so maybe the actual order will be different.
That's the same ordering as the running times for the current record holder machines, which also seems like a relevant heuristic.
This ordering also matches the number of remaining holdouts.
/EvanDaniel/how-many-holdout-machines-will-ther
That said, these three all have cryptids. Maybe there's just some "luck" in which of the Collatz-like problems are easiest?
https://wiki.bbchallenge.org/wiki/Cryptids