Question & Answer: Prove by induction on n that if the TM (at right above) is started with a blank tape, 10 n + 5 steps the machine will be…..

I have uploade three Images for showing the steps for this TM process. In uploaded images you will see total 16 moves (steps) are explained with their abbreviations. Now In first Image After 5 step tape will be like

…00011100… , It is currently at 4 state and symbol encounterd on tape is 0 (little typo in image explanation it is written as 1 but it should be zero)

* Trailing dots above indicates trailing zero or blank cells.

and head will be at the first zero preceding first one. Now Again we start iterating for next moves and at 10th step we will have tape reading like

..0011100…

and head will be at the last zero mentioned here. and current state is 0 with input 0

Now at 15th step i.e, after a interval of 10 step it will again start behaving as it is started from initial step. String on tape is like

…011101110…

and the head is at the zero which is between above 2 alternate and adjacent 1s.

Recall at 5th step string was

…000111000…

Now we can see that at 10 step we can make our string as 0(0111)01110 which is basically 0(0111)¹01110

Similarly at 5th step same string forms which can be grouped as 0(0111)⁰01111. Since here the actual string is …0111..

So by Induction It can be shown that this will never going to halt and will repeat its bh=ehaviour after 10n+5 steps where n starts from zero.