What is meant by "dovetailing"?

Question

While reading the reviews for Stephen Wolfram's "A New Kind of Science" on Amazon, I came across the following statement:

Every computer science (CS) student knows the dovetailer, a very simple 2 line program that systematically lists and executes all possible programs for a universal computer such as a Turing machine (TM).

Can someone give a "simple 2 line program" which illustrates "dovetaling"?

Marin

Answer 1

A CS student usually has on hand an encoding of Turing machines to integers, which they need when they write their software Turing machine emulator that takes as input a Turing machine, and writes as output the output of the specified machine. It's possible to arrange that this encoding has the property that every integer is a different, valid program.

So the naive two-liner to list and execute all programs would be:

for (int i = 0; ; ++i) 
    printf("%d: %d\n", i, universal_turing_machine(i));

This ignoring that in C, int is a fixed-width type.

Now, obviously that program doesn't get very far, because quite soon it hits an i for which the corresponding Turing machine doesn't halt. So the "dovetail" trick is to run one instruction from the first machine, then an instruction from the second and another from the first, then one each from the third, second, first, and so on. As each machine halts (if it halts), of course you can stop processing it or just sit doing nothing in its "timeslices".

I don't know quite how that's a "two-liner", considering the context switch necessary between Turing machines at each step. But the dovetail program has theoretical use (and probably no use in practice). One interesting thing about it is that it has the following property:

If there exists a program P which solves a problem X in polynomial time (and provides the information necessary to prove the solution), then the dovetail program solves X in polynomial time.

The proof is fairly simple (it takes constant time equivalent to executing P*(P-1)/2 Turing instructions to reach the start of the correct program P[*], and then only polynomially worse time to execute it than it would take to execute that program on its own). The re-statement of the property that I find most amusing is:

If P=NP, then we already know polynomial solutions to all NP-complete problems.

We just haven't yet proved they're polynomial. A proof of P=NP would complete that proof without actually exhibiting which of the sub-programs it is that solves the problem. The dovetail program itself can figure that out as it goes - when each machine halts, use the polynomial-time "is this a solution to X for the original input?" algorithm that's implied by X being NP. If it is a solution, output and halt. If it isn't, keep going.

[*] Well, maybe linear time, since as you create each new virtual Turing Machine, you need to give it a copy of the input to work on. Also in practice the context switches probably aren't constant time, so call it quadratic. Hand-wave-hand-wave it's polynomial OK?

Uppercase

Answer 2

Well, a turing machine program is, in fact, a table (state x tape symbol), so the program would just enumerate all such possible tables. like that:

for(int symbol_count = 1; true; symbol_count++)
{
    for(int state_count = 1; state_count <= symbol_count; state_count++)
    {
        gen_table(symbol_count, state_count);
    }
}

where gen_table enumerates all the action tables of such size (for example, treating the table as a big number and states as digits). That's longer than two lines in C, probably, Wolfram used some other, more powerful language.

Enquire