Busy beaver lemma

77 Views Asked by At

Let $p(n)$ be the productivity of the most productive $n$-state machine, where the productivity $f$ of a TM is defined to be the length of the $*$-string if the TM halts in standard position and 0 otherwise.

I'm trying to prove: $$ \forall n [p(n+11) \geq 2n ] $$

Presumably I have to construct an $n$-state turing machine that produces a string of $n$ $*$-symbols. But I'm not totally sure how to do this, or how to proceed.