LinkBack URL
About LinkBacks
The busy beaver function is well known, but to be specific, let me define the busy beaver function BB(n)= maximum number of 1's that can be printed on the tape by a standard n-state, 2-symbol halting Turing machine before halt.
My question maybe trivial: is it true that BB(n+1)>BB(n) for all n?
The claim is true if we measure the busy beaver by BB'(n)= maximum number of shifts made by the machine before halt. (This is because we can always change the last shift made by BB'(n), say, to
and
, thus making sure that BB'(n+1)
BB'(n)+1
BB'(n)). Can we show that the strict inequality holds too if we measure by scores instead of by shifts?
