Prove by induction on n that if the TM (at right above) is started with a blank tape, after 10 n + 5 steps the machine will be in state 4 with the tape reading … 0(0111)^n01110 That is, although there are three states with halting instructions, show why none of those instructions is actually encountered, and formulate this into a proof that this machine does not halt when started with a blank tape.
Expert Answer
The induction step is to show that if 10n+5 steps take you to state 4 with a tape
…0(0111)n01110…,
then 10(n+1)+5 steps take you to state 4 with a tape
…0(0111)n+101110….…
Checking this is just like checking that if you’re in state 4 and have a tape …01110…, and you go 10steps, you end up in state 4 with a tape …011101110: just write down the 10combinations 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.