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) 01110. 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.

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

 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

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

Still stressed from student homework?
Get quality assistance from academic writers!