how would I go about proving by induction that the Turing Machine pictured below, that if it is started with a blank tape, after 10n+6 steps the machine will be in state [3] with the tape reading
. . . 0(0111)^n0110...
Any help is appreciated, thanks :)
Check that after $6$ steps we’re in state $3$, and the tape has $\ldots 0\color{red}{1}110\ldots\;$, where the red cell is the current location of the read/write head. Check that after another $4$ steps we’re in state $0$, and the tape has $\ldots 01110\color{red}{0}0\ldots\;$. Then check that the next $6$ steps proceed just like the first $6$, and we end up in state $3$ with a tape $\ldots 01110\color{red}{1}110\ldots\;.$ So far, then, we we’ve seen that after $10n+6$ steps we end up in state $3$ with a tape $\ldots 0(0111)^n0\color{red}1110\ldots$ if $n=0$ or $n=1$. (Note that you’re missing a $1$ in your statement of the problem: the final block should have three $1$s, not two.)
The induction step is to show that if $10n+6$ steps take you to state $3$ with a tape
$$\ldots 0(0111)^n0\color{red}1110\ldots\;,$$
then $10(n+1)+6$ steps take you to state $3$ with a tape
$$\ldots 0(0111)^{n+1}0\color{red}1110\ldots\;.$$
Checking this is just like checking that if you’re in state $3$ and have a tape $\ldots 0\color{red}{1}110\ldots\;,$ and you go $10$ steps, you end up in state $3$ with a tape $\ldots 01110\color{red}{1}110\ldots\;$: just write down the $10$ combinations of state and tape. You’ll find that the read/write head never moves far enough to the left to interfere with the $(0111)^n0$ part, so you’ll be able simply to carry it along.