How large must $S(5)$ be at least , if it is not $47,176,870\ $?

Question

See here :

https://en.wikipedia.org/wiki/Busy_beaver

for more details about the maximum-shifts-function

It is said that about $40$ machines with $5$ states have unknown status (it is not known whether they eventually halt or not).

I am pretty sure, that those machines have been simulated and ran for a long time.

Is there any reference giving at least an approximate value, how many steps the machines make at least ?

In other words :

If $S(5)>47,176,870\ $ holds, what is a lower bound for $S(5)$ ?

Answer 1

I believe you are referring to Georgiev's analysis of 5-state Turing machines; he wrote a program that was able to resolve the halting behavior of all but 164 5-state Turing machines, and he then reduced that number down to 42 with individual analysis.

User Ikosarakt1 of the Googology Wiki ran each of those 42 machines for 10 billion steps, and none of them halted, so we could presumably conclude that either S(5) = 47,176,870 or it is more than 10 billion. (See here.)

A couple of caveats: According to Daniel Briggs, Georgiev mislabelled one of the 164 machines and there should actually be 43 unresolved machines. So we would need to evaluate the 43rd machine for 10 billion steps to make the previous claim. Also, it appears that Georgiev's work has not been verified, so perhaps we should take the claim that all but 42/43 5-state Turing machines have been resolved with a grain of salt until independent verification occurs.

Answer 2

It saddens me to answer your question by the negative : I could not find any description of the 'holdout' TMs, i.e. those for which we do not know if they ever halt.

As far as I can tell, people just publish their Busy Beaver champions, but not much else.

For exemple Heiner Marxen's website gives a lot of long running TMs that halt.

I found a paper complaining about that state of affairs, though : https://arxiv.org/abs/1602.03228 quote:

"Whilst there is no reason whatsoever to doubt the veracity or sincerity of these results and others like them in the literature, it seems unscientific to accept such results as proven in the absence of both mathematical proof and empirical evidence that can be inspected, assessed and checked. [...] This evidence should include not only the programs used for the search, but also the list of machines generated as well as the evidence used to draw conclusions about their status."

About your comment/edit, indeed if hypothetically any holdout TM eventually halts, that doesn't tell us anything about $\Sigma(5)$ because the number of ones on the tape doesn't necessarily grow with the number of steps. So the next $S(5)$ champion could have $4099$, $Ackerman[5,2]$, or $3$ ones on the tape, for all I know.