# Answered! 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…

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.

Check that after 5 steps we’re in state 4, and the tape has …01110…… 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 …0111000……Then check that the next 66 steps proceed just like the first 5, and we end up in state 4 with a tape …011101110….… So far, then, we’ve seen that after 10n+5 steps we end up in state 4 with a tape …0(0111)n01110……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 1s, not two.)

The induction step is to show that if 10n+5 steps take you to state 4 with a tape

Don't use plagiarized sources. Get Your Custom Essay on
Answered! 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…
GET AN ESSAY WRITTEN FOR YOU FROM AS LOW AS \$13/PAGE

…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.