Dovetailing technique

Dovetailing is a technique for handling an infinite number of items (or an infinite number of computations) by interleaving them, so that each one gets attention after a finite delay. Instead of finishing the first item completely (which may never end), we do a little of item 1, then a little of items 1 and 2, then a little of items 1, 2, 3, and so on.

Example 1: N × N is countable

Arrange the pairs (i, j) in a grid and list them along the diagonals i + j = 0, 1, 2, ...

        j=0   j=1   j=2   j=3
 i=0   (0,0) (0,1) (0,2) (0,3)
 i=1   (1,0) (1,1) (1,2)
 i=2   (2,0) (2,1)
 i=3   (3,0)
Order: (0,0) (0,1) (1,0) (0,2) (1,1) (2,0) ...

Every pair appears at a finite position, so N × N is countably infinite. Counting positions from 0, the position of (i, j) is (i+j)(i+j+1)/2 + i. The same idea shows that a countable union of countable sets is countable, and that Q is countable.

Example 2: simulating infinitely many machines

To find whether some input makes a Turing machine halt (or to enumerate a recursively enumerable language), run in stages:

Stage 1: 1 step  on input w1
Stage 2: 2 steps on w1, 2 steps on w2   (restart or continue)
Stage 3: 3 steps on w1, w2, w3 ...

If any computation halts after t steps on input wᵢ, we find it at stage max(i, t). A computation that loops forever cannot block the others.

Uses: proving countability, showing that the union of two r.e. languages is r.e., and simulating nondeterministic TMs by deterministic ones.