Skip to content
Home » Diagonal Argument

Diagonal Argument

1. Definition

The Diagonal Argument is a mathematical technique introduced by Georg Cantor to show that some infinite sets are larger than other infinite sets.

In Theory of Computation, it is important because it helps explain that:

There are more possible problems/functions than there are computer programs to solve them.

Therefore, some problems cannot be solved by any computer or algorithm.


2. Basic Idea — Very Simple

Suppose we make a list of things:

1234
10110
21001
31100
40011

Now look at the diagonal elements:

0, 0, 0, 1

Change each value:

  • 0 → 1
  • 0 → 1
  • 0 → 1
  • 1 → 0

We get:

1, 1, 1, 0

This new sequence is different from every sequence in the list, because it differs from the first sequence at position 1, second at position 2, third at position 3, etc.

Therefore, the original list cannot contain every possible sequence.


3. Why is it called “Diagonal”?

Because we take elements along the diagonal of the table:\[ (1,1),(2,2),(3,3),(4,4),… \]

Then we change those elements to construct something not present in the list.


4. Connection with Theory of Computation

The diagonal argument is used to prove that:

Not every mathematical problem can be solved by a computer.

Imagine we make a list of all possible computer programs.

Now suppose every possible problem could be solved by one of these programs.

Using a diagonal-type construction, we can create a problem that behaves differently from the program assigned to it.

This produces a contradiction.

Therefore:

Some problems are not computable.


5. Importance

The diagonal argument helps us understand:

  • Limits of computation
  • Existence of non-computable problems
  • Undecidable problems
  • Limits of algorithms
  • Foundations of computability theory

It is also closely related to the proof of the Halting Problem.


⭐ Exam Answer — 5–10 Marks

The Diagonal Argument is a mathematical technique introduced by Georg Cantor. It is used to prove that some infinite sets cannot be completely listed or matched with another set.

In the argument, elements of a list are arranged in a table. The diagonal elements are selected and changed to construct a new element. The new element differs from the first element at the first position, the second element at the second position, and so on. Therefore, the newly constructed element cannot be present anywhere in the original list.

In Theory of Computation, the diagonal argument is important because it helps prove that there are problems that cannot be solved by any algorithm. Thus, it demonstrates the limitations of computation and is related to the study of undecidable and non-computable problems.

🧠 One-line memory trick

“Take the diagonal → change it → get something not in the list → therefore the list cannot contain everything.”