Print
Category: Others
Hits: 2876

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:

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