Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.