In computability theory, dovetailing is a method that lets you simulate running multiple programs in parallel, even when there are infinitely many programs to run. This is absolutely crucial because of the non-computability of the Halting Problem.
Suppose you have an infinite number of Turing Machines T1, T2, … and you want to check whether any of them output “0″ when run on a blank tape. A naive solution would be to begin running T1 until you get an output, check whether it’s “0″, if not then begin running T2, and so on. The problem is, T1 might never halt, and there’s no way for you to determine whether or not it’s ever going to halt.
The Dovetailing solution is like this: you run T1 for one step. Then you run T1 for two steps, followed by T2 for one step. Next, run T1 for three steps, followed by T2 for two steps, followed by T3 for one step. And so on. In the kth iteration, you run T1 for k steps, you run T2 for k-1 steps, …, and you run Tk for one step. If any of the machines will ever output “0″, you’ll eventually see it. (More precisely, if Tk outputs 0 after N steps, you’ll see this on the (N+k-1)th iteration, assuming you don’t see a different 0 earlier.)
If the ordered sequence (T1,T2,…) is recursively enumerable, you can even go so far as to create a single machine which does all this checking for you. In fact, you can create a machine which accepts an arbitrary input N and then checks whether any of the machines listed by the Nth machine ever output “0″ on the blank tape. You can do all kinds of crazy stuff with dovetailing.
Application to Complexity Analysis
Suppose you’ve got two algorithms. Algorithm A runs in probabilistically-expected time O(n^2) but in the worst-case scenarios, can take as long as O(n^4). Algorithm B runs in time O(n^3). Can you get the best of both worlds? Yes! You can dovetail the two algorithms together to simulate running them in parallel. (The dovetailing described above should be altered slightly: rather than starting over from scratch each time you return to one of your algorithms, start it where you last left it off) Thus, run one step of A, followed by one step of B, one step of A, one of B, and so on until one of them finishes. Now you’ve got yourself an algorithm with probabilistic-expected runtime O(n^2), and you’ve whittled its worst-case runtime down to O(n^3)!
Of course, only a theorist would think of something like this, since in practice the dovetailed algorithm would tend to be twice as slow as algorithm A, even though they have the same probabilistic big-O runtime.
Dovetailing Research
In some sense, all academic research is dovetailed. We do not know what the optimal strategy is for attacking an open problem like the Riemann Hypothesis. We could choose one strategy and have the entire mathematics community pursue it single-mindedly. And if that strategy turned out to be the best one, or even within three or four orders of magnitude of the best one, this would get us a solution faster. However, it’s also possible that the strategy is a “non-halting Turing Machine”, that it never leads to the solution, and that pursuing it is a waste of time.
So instead we dovetail. We spend some time following one strategy, then we move to the next, and then the next… presumably, if a strategy hasn’t been completely exhausted, somebody will eventually get around to pushing it a little further… and we hope that at least one of the strategies works, and that we aren’t in the situation where NONE of the machines reaches a desired outcome!
FURTHER READING
Turing Machines
Levels of Infinity
Obtaining Strong Recursion from Weak Recursion