I was going through TM here and encountered a term "Dovetailing".

What is exactly the dovetailing in Turing Machines?

Can anyone mind to provide a good explaination with some examples?


Dovetailing is when you simulate two or more Turing machines in parallel on a single Turing machine. Your operating system uses this technique all the time.

Why is dovetailing useful? Here is one example. Suppose that $L$ is recursively enumerable (there is a Turing machine enumerating all words in $L$) and also co-recursively enumerable (there is a Turing machine enumerating all words not in $L$). Then $L$ is recursive (there is a Turing machine that, given a word $x$, decides whether $x \in L$). For the proof, we simulate the first two machines in parallel, wait for $x$ to appear, and the answer accordingly.

How is dovetailing implemented? Typically, we alternately simulate one step of each machine.

In contrast to your operating system, in theoretical computer science we are sometimes interested in dovetailing infinitely many computations. This can be accomplished by running the first machine for one step, then the first two machines for one step, then the first three machines, and so on. Perhaps you will encounter examples illustrating why this is useful later in your academic life.

  • $\begingroup$ Can i use dovetailing here ? L = { < M1,M2 > | M1,M2 are TM's and Ɛ ∈ L(M1) ∪ L(M2) } $\endgroup$ – Garrick Oct 6 '16 at 5:34
  • $\begingroup$ I think i can dovetail between M1 and M2 and know if any one accepts epsilon, making it RE language . $\endgroup$ – Garrick Oct 6 '16 at 5:35
  • $\begingroup$ I have one more example that confuses me . Can we apply this techniques here ? L = { < M1,M2 > | M1,M2 are TM's and L(M) = L(M1) ∪ L(M2) } $\endgroup$ – Garrick Oct 6 '16 at 5:37
  • $\begingroup$ Why is this called dovetailing? $\endgroup$ – adrianN Oct 6 '16 at 7:24
  • 1
    $\begingroup$ @adrianN, because you alternate execution of two machines. It's named after a dovetail joint: upload.wikimedia.org/wikipedia/commons/thumb/6/6a/… (notice the alternation at the join point). $\endgroup$ – D.W. Oct 6 '16 at 17:14

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.