# Proving a language is Turing recognizable

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.

-
Please explain what WAIT means here. A Turing machine lives alone in it's universe, there is nothing else which could make the WAIT end, so I'm lost. –  vonbrand Feb 19 '13 at 2:17
@vonbrand: It seems to make the best sense to interpret "wait" as an alternative to "left" and "right", such that one can specify "in state $s_1$, seeing symbol $a_1$, write $a_2$ and go to state $s_2$ without moving the tape head". –  Henning Makholm Feb 19 '13 at 13:46
@HenningMakholm, that can be simulated by e.g. writing $a_2$ and move right, there write the symbol that is already there and move left. –  vonbrand Feb 19 '13 at 15:41

Take a machine $M$ with wait instructions, and transform it into a machine $M'$ that does the same thing but without using wait. For example, suppose when $M$ is in state $S$ and scans symbol $i$ on the tape, it goes into state $T$ and the head waits. 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 using wait to hold the tape head still, it moved it right and then left.

-