Index of Beaver Function


1. Definition

A busy beaver is a turing machine, witch writes the maximum possible number of 1s to its output tape without ending in a infinite loop. Only infinite loops can write more 1s. The input alphabet is S={0,1}, where as the output tape is initialized with zeros.

The Beaver Function E(n) returns the number of 1s a busy beaver Tn, can write to its output tape. Tn contains exactly n states and one final state. The function is defined, if the turing machine reaches the final state (halts), and it's not defined if the turing machine never stops (endless loop).

E(n) = kn

For example a busy beaver T1 with |Q\{qf}|=1 goes immediately into the final state writing one stroke to the tape. Therefore the Beaver Function E(1)=1.

2. Computability

The beaver function can not be computed with any turing machine. To proof this we first assume there exists such a Turing Machine Tbe and then we show by contradiction that it can not exist.

So lets assume the turing machine Tbe can compute the beaver function. This means giving a nature number n (number of states of a busy beaver) returns E(n). We also know that E(n) is the maximum number of strokes any existing turing machine with n states can write to its output tape. Only non terminating turing machines can write more strokes to their output tapes.

Having such a function we could simply test if any turing machine with n states will halt or not, by building a turing machine TH it in the following way:

  • TH can simulate any turing machine (derived from the universal turing machine).
  • We add a new tape to the TH, witch is initialized with E(n)+1 at the beginning.
  • For each simulation step of the simulated turing machine T, we remove a stroke from the second tape.
  • We check after each step if the second tape is empty. If so, this means we simulated more steps than E(n). Therefore we know that this turing machine would never stop. Our TH will stop state qN . If the simulation stops (and therefore the tape can not be empty), TH will stop in qY.

So we somehow built a decider for the most famous halting problem. But because we proofed earlier that the halting problem can not be decided, there must be a contradiction of in our construction. Since the introduced step counter will really count the simulated steps of any turing machine T, there is only one assumption left: "there would exist a turing machine Tbe". Therefore Tbe can not exist.


input T, x:
begin
  m:= 1;
  while(true)
    execute m transitions of T on x
    if actualstate element of F
      return 'halted'
    if m >= m S(n)
      return 'will never halt'

    m = m + 1;
  end
end