Can a machine exist making more steps than the current record, which is no busy beaver?

104 Views Asked by At

There are some machines in the busy-beaver-competition for turing machines with $5$ states and $2$ symbols for which it is not known whether they halt or not.

Is it possible that among those machines, there is a halting machine beating the current record with respect to the number of steps, but not being a busy beaver beacuse it doesn't write down more ones than the currect record ? Or do we know that such a halting machine would also be a new record holder with respect to the number of ones ?

I tend to believe that we cannot rule out this possibility. In fact, I am not sure whether we can even rule out any final output (except trivial ones like an empty tape, if the machine contains $1RH$ forcing at least one $1$ on the tape).

2

There are 2 best solutions below

3
On

I don't know the exact machines in the competition, but in general the answer could be "we have a machine which isn't known to halt or diverge, which we've been running for years but has written down fewer 1's so far than the best-known busy-beaver candidate". In that case, exactly one of the following is true, but we don't know which:

  • The machine halts, leaving the tape with more $1$'s than the current record holder. Then it is a busy-beaver record beater.
  • The machine halts, but does not leave the tape with more $1$'s than the current record holder. Then it is not a busy-beaver.
  • The machine diverges. Then it is not a busy-beaver candidate at all, let alone a record-beater.
0
On

I would say that yes, this is perfectly possible. We know that the champion as far as the number of $1$'s written at the end does not need to be the same as the champion in terms of steps taken (here are some champions for the quadruple definition Turing machines, and the champion for $1$'s is not the same machine as the champion for steps)

So, the situation you describe is can certainly be true at the beginning of our investigations, when every machine is a holdout ... so why would that change later on, assuming we still haven't found neither the $1$-champion nor the step-champion?