• A Turing machine has a two-way infinite tape, made of cells.
  In each cell, there is a symbol.
  There is a finite number of symbols, denoted by 0, 1, ...
  The symbol 0 is the blank symbol.
  Initially, the Turing machine holds a finite input.
  This input is a string of symbols, for example: 101001.
  The other cells of the tape hold blank symbols.
  In the kind of machine we consider, the input can contain the blank symbol 0.

  . . .

  0

  0

  1

  0

  1

  0

  0

  1

  0

  0

  . . .

• A Turing machine has a tape head.
  With this tape head, the machine can read and write on the tape.
  The tape head moves one cell left or right at each step.
  These directions are denoted by L and R.
  In the kind of machine we consider, the tape head cannot keep still.
  Initially, the tape head scans the leftmost symbol of the input.

• A Turing machine has a finite number of states.
  The states are denoted by A, B, C, ...
  In addition to these states, there is a special state, the halting state, denoted by H.
  Initially, the state is A, so A is called the initial state.
  Below, you can see the initial configuration of a Turing machine on the input 101001:

  . . .

  0

  0

  A 1

  0

  1

  0

  0

  1

  0

  0

  . . .

  The position of the tape head is indicated by writing the current state on the scanned cell.

• A Turing machine has a next move function.
  The next move function says that, when the machine is in state q and scans symbol a on a cell, then the machine writes a symbol b instead of a, moves one cell in the direction left or right, and enters state p.
  We suppose that, when the machine stops, it writes a 1, moves right, and enters state H.
  The next move function is given by a table.
  For example, we give below the table of a machine from Lin and Rado, with 3 states A, B, C, and 2 symbols 0, 1, and the computation of this machine on an initially blank tape.

The machine stops in 14 steps, leaving 6 symbols 1 on the tape.

• Formal mathematical definition.
  Let S = {0,1,...} be the finite set of symbols, and let Q = {A,B,...} be the finite set of states.
  Then the next move function is a mapping
  

  d : Q ×  S  ---> S × {L,R} ×  Q   or    {(1,R,H)}.

  For example, if   d(A,0) = (1,R,B),  then it means that, when the machine is in state A scanning symbol 0 on a cell, then it replaces 0 by 1 on this cell, moves one cell right, and enters state B.

• Consider Turing machines with fixed numbers of states and symbols.
  If there are k states and n symbols, then the number of possible next move functions, or possible tables, is (2kn+1)^kn.
  Thus, there are (2kn+1)^kn Turing machines with k states and n symbols.
  Each of them can be launched on a blank tape, that is a tape with symbols 0 in all cells.
  Then some of them never stop, and the other ones eventually stop.
  Those which stop are called busy beavers.

• Busy beavers compete in two competitions:
  • to take the most time to stop,
  • to leave the most non-blank symbols on the tape when stopping.

  We denote by s(M) the time taken by busy beaver M, and by sigma(M) the number of non-blank symbols left on the tape by M.
  We denote by S(k,n) the time taken by the busy beaver with k states and n symbols which takes the most time to stop:
  

  S(k,n) = max {s(M) : M is a busy beaver with k states and n symbols}

  We denote by Sigma(k,n) the number of non-blank symbols left on the tape by the busy beaver with k states and n symbols which leaves the most non-blank symbols on the tape when stopping:

  Sigma(k,n) = max {sigma(M) : M is a busy beaver with k states and n symbols}

• Example: the Lin and Rado's Turing machine given above, with 3 states and 2 symbols, takes 14 steps to stop, and leaves 6 symbols 1 on the tape when stopping.
  So here: s(M) = 14 and sigma(M) = 6.
  This machine is the winner for the most non-blank symbols left on the tape, so we have Sigma(3,2) = 6.
  It is not the winner for the most time: another machine takes 21 steps to stop, and we have S(3,2) = 21.

• In 1936, Turing defined Turing machines as a universal model of computation on natural numbers. This means that all computable functions you can imagine can be computed by a Turing machine.
  Other authors (Church, Kleene, Post, Markov) defined other models of computation, but these models compute the same functions as Turing machines.
  So it is currently assumed that "computable" means "computable by a Turing machine". This assumption is called Church's Thesis, or, more accurately, Church-Turing Thesis.

• Then, how to find a non-computable function?
  Such a function can be defined from a model of computation by an abstract device called diagonalization method. But usually this method does not give an explicit function.
  Here enter busy beavers.

• In 1962, Rado defined busy beaver competition. He considered Turing machines with 2 symbols, and defined the functions S(n,2) and Sigma(n,2). He proved that these functions are not computable. Moreover, these functions grow faster than any computable function (that is, for any computable function f, there is an integer N such that, for all n > N, we have S(n,2) > f(n)).
  The definitions of functions S(n,2) and Sigma(n,2) are explicit enough to allow their computations for small n. The promise is to get quickly large numbers. So winning busy beavers are simply definable machines with complex behavior. That's why they are interesting.