in Theory of Computation
6 votes
6 votes
can someone explain Dovetailing in TOC in simple terms and with examples

what it is?

why and where it is used?

how it is used and how to visualize it ?
in Theory of Computation

2 Answers

8 votes
8 votes
Best answer

Firstly what is dovetailing :

Dovetailing is when you simulate two or more Turing machines in parallel on a single Turing machine. 

Why do we need it?

Suppose you have a TM for a Recursively Enumerable Language (Mind that, a TM for a RE language on a given input string may halt or may go into an infinte loop).Now suppose you want to create an enumerator for this TM.

What is an Enumerator?

Suppose you want the list of strings which are accepted by a TM constructed for a certain language, then you construct the TM and then print all the strings which are accepted by the TM.This process is called enumeration.

So you feed strings one after another to this TM (Constructed for this RE language) and print all those strings which are accepted by the machine.Now, while doing this you may feed it a string for which the TM goes into an infinite loop, thus now you cannot proceed further as it is struck.But an enumerator actually exists for an RE language and it is made possible by using the dovetailing method.

In this method we have many turing machines(all constructed for the same RE language) and we feed different strings to each of them.Further we analyze the output of each of them step by step and parallelly, such that :

  • Suppose we have 10,000 strings and 10,000 TM's
  • When the 1st string is at 10,000 th step of execution
  • The 2nd string is at 9999 th step of execution
  • And the 10,000 th string is at 1st step of execution.
  • Further if at any step the machine accepts then we print the string.
  • All of these is happening simultaneously(parallelly).

Thus due to this method if for any string the TM would have gone into infinite loop for a single TM arrangement, here, due to simultaneous step by step arrangement, we do not encounter this problem because for those strings (infinite loop one) we go to the next step of execution and simultaneously we check for other valid strings in other TMs. 

selected by
0 votes
0 votes
In TOC Dovetailing  stands for Non-determinstic Turing Machine