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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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