Dovetailing
Let us consider another example where we are given a Turing Machine M. It is also given that M accepts at least one string from Σ*. The task is to determine which string is accepted by M.
Any of the above algorithms will not work in this case. We have to simulate M in the following way:
- Arrange all the strings of Σ* in lexicographical order.
- Iteration 1(T1 in the image) : Take out one string w1 from Σ*, run M on w1 for 1 step
- Iteration 2(T2 in the image): Take out another string w2 from Σ*, run M on w2 for 2 steps, and run M on w1 for 1 more step.
- Iteration 3(T3 in the image): Take out another string w3 from Σ*, run M on w3 for 3 steps, run M on w1 for 1 more step, and run M on w2 for 1 more step.
- …..
- …..
- Iteration n: Take out a string w(n) from Σ*, run M on w(n) for n steps, and run M from w1 to w(n-1) for 1 step each.
Visualization of dovetailing through image
By interleaving all the inputs in this way we will be able to determine the only string from Σ* that is accepted by M in a finite amount of time. This special type of interleaving technique is known as dovetailing.
Dovetailing in Turing Machines
In the carpentry industry, dovetailing is a technique of joining two pieces of wood together by interleaving them. Similarly in the case of Turing Machines dovetailing is the technique by which we can simulate multiple Turing Machines, in some cases an infinite number of Turing Machines together.
This technique can be very useful in determining the decidability and recognizability of some Turing Machines or languages related to Turing Machines.