The Busy Beaver Function Σ
The busy beaver function, Σ: N → N, is defined such that Σ(n) is the maximum attainable score (the maximum number of 1s finally on the tape) among all halting 2-symbol n-state Turing machines of the above-described type, when started on a blank tape.
It is clear that Σ is well-defined function: for every n, there are at most finitely many n-state Turing machines as above, up to isomorphism, hence at most finitely many possible running times.
This infinite sequence Σ is the busy beaver function, and any n-state 2-symbol Turing machine M for which σ(M) = Σ(n) (i.e., which attains the maximum score) is called a busy beaver. Note that for each n, there exist at least two n-state busy beavers (because, given any n-state busy beaver, another is obtained by merely changing the shift direction in a halting transition).
Read more about this topic: Busy Beaver
Famous quotes containing the words busy, beaver and/or function:
“The light by which we see in this world comes out from the soul of the observer. Wherever any noble sentiment dwelt, it made the faces and houses around to shine. Nay, the powers of this busy brain are miraculous and illimitable.”
—Ralph Waldo Emerson (1803–1882)
“On the top of the Crumpetty Tree
The Quangle Wangle sat,
But his face you could not see,
On account of his Beaver Hat.”
—Edward Lear (1812–1888)
“The mother’s and father’s attitudes toward the child correspond to the child’s own needs.... Mother has the function of making him secure in life, father has the function of teaching him, guiding him to cope with those problems with which the particular society the child has been born into confronts him.”
—Erich Fromm (1900–1980)