---
title: "Dovetailing technique"
subject: "Theory of Computation"
chapter: 1
key: "semester_3/theory_of_computation:dovetailing-technique-explain"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/dovetailing-technique-explain
site: BCT Engineering
---

# Dovetailing technique

Theory of Computation · Chapter 1: Introduction

- Asked in: 2073 Chaitra
- Video: [Dovetailing](https://www.youtube.com/watch?v=zBFQaEivPko) — CS360S21
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/dovetailing-technique-explain
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-1

## Question

Explain the dovetailing technique.

## Short answer

Dovetailing interleaves infinitely many tasks so that each progresses after a finite delay. For example, listing pairs (i,j) along diagonals shows N×N is countable. It is used to simulate multiple Turing machines or to prove a countable union of countable sets is countable.

## Answer

**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, ...

```text
        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:

```text
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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is dovetailing?
   A. Running only the shortest computation
   B. Finishing the first item completely before the next
   C. Sorting items by size
   D. Interleaving infinitely many items or computations so each gets finite-time attention
   Answer: D. We do a little of item 1, then 1 and 2, and so on. (Key point: Idea)

2. How is N × N shown countable by dovetailing?
   A. List pairs along diagonals i + j = 0, 1, 2, ...
   B. Pair each i with i^2
   C. List row 0 completely, then row 1
   D. List column by column from the largest
   Answer: A. Each pair appears at a finite position along its diagonal. (Key point: N × N)

3. Why can we not run each TM on all inputs to completion one at a time?
   A. TMs cannot read more than one input
   B. It would use too much memory
   C. A looping computation would block all the later ones forever
   D. Halting is always decidable
   Answer: C. Dovetailing ensures a loop cannot block others. (Key point: Why not sequential)

4. If a computation halts after t steps on input w_i, at which stage is it found?
   A. Stage i + t
   B. Stage t only
   C. Stage max(i, t)
   D. Never, if any other computation loops
   Answer: C. By stage max(i, t) w_i has been run for at least t steps. (Key point: Halting stage)