Cheap and Secure Web Hosting Provider : See Now

[Answers] How can a Turing machine run another machine for an infinite amount of strings?

, , No Comments
Problem Detail: 

The proof in my textbook, that $E_{TM}$ can be decided by oracle machine $O^{A_{TM}}$, uses a Turing machine $P$ such that for an input $w$:

  • $P$ runs the Turing machine $M$ on all strings of $\Sigma^*$
  • If $M$ accepts the string, $P$ accepts

$O^{A_{TM}}$ then asks the oracle if $<P,w> \in A_{TM}$

I can't seem to understand why $P$ can run $M$ for all strings of $\Sigma^*$ because this is an infinite amount of strings. I do, however, understand that $P$ actually never has to run and is purely constructed to ask the oracle if it accepts.

Asked By : Barney Kelly

Answered By : Yuval Filmus

The technique is knows as dovetailing. The machine $P$ keeps a two-dimensional tape and uses the following algorithm:

  1. Run $M$ on the first string for one step.
  2. Run $M$ on the first two strings for one step.
  3. Run $M$ on the first three strings for one step.
  4. ...

(We imagine that all possible strings are arranged in some arbitrary computable order, say $\Lambda,0,1,00,01,10,11,000,\ldots$.)

Each simulation of $M$ runs on its own "row" of the two-dimensional tape of $P$, which also stores the location of the head and the current state. (A two-dimensional tape can be simulated by a one-dimensional tape.)

If $M$ ever halts on one of the strings, then $P$ halts. Therefore $P$ halts iff $M$ halts on some input.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback