The busy beaver is a well-known specific example of a non-computable function. Whilst many aspect of this problem have been investigated, it is not always easy to find thorough and convincing evidence for the claims made about the maximality of particular machines, and the phenomenal size of some of the numbers involved means that it is not obvious that the problem can be feasibly addressed at all. In this paper we address both of these issues. We discuss a framework in which the busy beaver problem and similar problems may be addressed, and the appropriate processes for providing evidence of claims made. We also show how a simple heuristic, which we call the observant otter, can be used to evaluate machines with an extremely large number of execution steps required to terminate. We also show empirical results for an implementation of this heuristic which show how this heuristic is effective for all known monster' machines.
About the relation between the shift function S(n) and the busybeaver function Σ(n), there have been some results. In 1992,A. Julstrom gave his result: S(n) < Σ(20n); in 1994, WangKewen and Xu Shurun obtained: S(n) < Σ(10n). In thispaper, we shall show that S(n) ≤ Σ(3n -f c)(c is aconstant). The Busy Beaver function S(n) is the maximum number of 1's a halting n-state Turing machine may leave on an initially blank tape. The shift function S(n) is the maximum number of moves such a machine may make before it halts. This paper shows that S(n) l S(20n), then uses this result to prove that both S(n and S(n) are non-computable and their non-computability is equivalent to the undecidability of the halting problem. Demonstrations that several other functions are also non-computable apply a construction used in the proof of the bound on S(n). Consider Turing machines that use a tape infinite in both directions, with the tape alphabet 0,1 . Rado's busy beaver function, ones(n), is the maximum number of 1's such a machine, with n states, started on a blank (all-zero) tape, may leave on its tape when it halts. The function ones(n) is non-computable; in fact, it grows faster than any computable function. Other functions with a similar nature can be defined also. All involve machines of n states, started on a blank tape. The function time(n) is the maximum number of moves such a machine may make before halting. The function num(n) is the largest number of 1's such a machine may leave on its tape in the form of a single run; and the function space(n) is the maximum number of tape squares such a machine may scan before it halts. This paper establishes new bounds on these functions in terms of each other. Specifically, we bound time(n) by num(n+o(n)), improving on the previously known bound num(3n+6) . This result is obtained using a kind of self-interpreting'' Turing machine. We also improve on the trivial relation space(n) ≤ time(n) , using a technique of counting crossing sequences. Consider Turing machines that read and write the symbols 1 and 0 on a one-dimensional tape that is infinite in both directions, and halt when started on a tape containing all O's. Rado'sbusy beaver function ones(n) is the maximum number of 1's such a machine, withn states, may leave on its tape when it halts. The function ones(n) is noncomputable; in fact, it grows faster than any computable function. In this note we show how to construct some simply-configured N-state binary Turing machines that will start on a blank tape and eventually halt after printing a very large number of ones. The number of ones produced by these machines can be expressed analytically in terms of functional difference equation. The latter expression furnishes the best lower bound presently known for Rado's noncomputable function, Σ(N), when N ≫ 5.