Turing Machine M with a wait option has the option to make the machine's head wait where it is, until a case comes along where the wait option is not used. I am trying to show that such a Turing machine recognizes the class of Turing recognizable languages.
I have been trying to brainstorm how to begin to show this, however, I am having a difficult time proving this for the 'class' of Turing recognizable languages, as it is so general.
I would appreciate if someone can give me some suggestions, as to how I should proceed with this proof.
Many thanks in advance!
Take a machine $M$ with
waitinstructions, and transform it into a machine $M'$ that does the same thing but without usingwait. For example, suppose when $M$ is in state $S$ and scans symbol $i$ on the tape, it goes into state $T$ and the headwaits. Then $M'$ should have a state $S$, and when it scans symbol $i$ on the tape, it should go into state $S'$ and move the head to the right. Then in state $S'$ it should move the head left again, no matter what is on the tape, and go into state $T$. Now $M'$ goes into from state $S$ into state $T$ exactly like $M$ would have, except that instead of usingwaitto hold the tape head still, it moved it right and then left.