The lazy beaver function is a relative of the maximum shifts function[note 1] proposed by a commenter on Scott Aaronson's blog[1][2]. LB(n) is defined as the smallest number that is not the number of shifts made by an n-state Turing machine.

Bounds

It is known that LB(n) is less than or equal to TM(n)+1 where TM(n) is the number of n-state Turing machines. If it were greater, there would be a Turing machine with k shifts for all k from 1 to TM(n)+1, and that would require at least TM(n)+1 Turing machines. The bounds can be made even less because of isomorphic Turing machines that must have the same amount of shifts, and classes of Turing machines that do not halt.

Computability

The lazy beaver function is computable, because of the computability of the T-predicate.

Known values

  • LB(n) = S(n)+1 for n ∈ {1,2,3}
  • LB(4) = 72
  • LB(5) = 427
  • LB(6) = 33851[3]

Footnotes

  1. Aaronson usually refers to the maximum shifts function as the "busy beaver function", a term which on this wiki usually refers to the sigma function.

References

Community content is available under CC-BY-SA unless otherwise noted.