Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Proofs of the various hierarchy theorems in theoretical computer science (see e.g. are usually called diagonalization proofs. Why they are given this name?

When I look e.g. at the proof of the time hierarchy theorem, I can't see any connection to Cantor's diagonal argument, two-dimensional matrices or to diagonals in general. So where do diagonals come into play?

share|cite|improve this question
up vote 4 down vote accepted

In a typical proof of this sort, you are trying to construct a function $g(n)$ which is not equal to any function in some given sequence $f_i(n)$, $i = 0, 1, 2, \ldots$. In principle, to do that, you only need to show:

(*) For each $i$ there is a $n_i$ with $g(n_i) \not = f_i(n_i)$

Proofs of this kind are often called "diagonalization" informally by computability theorists; we have a very broad outlook on what "diagonalization" means.

Now, since you are constructing $g$, you have at least some control over it. To make the proof of (*) easier, you might go out of your way to make sure you know what $n_i$ will be, in terms of $i$; that makes the rest of the proof more direct. The simplest possible option is to construct $g$ in such a way that you can use $n_i = i$. That is the most "pure" kind of diagonalization.

If it is not straightforward to guarnatee $n_i = i$, you may at least be able to construct $g$ so that it is easy to pick some $n_i$ for each $i$. That is what is being done in the time hierarchy theorem proof linked in the question. Essentially, they need $n_i$ to be a sufficiently large index for a machine that computes the function $f_i$.

share|cite|improve this answer

One of the proofs in the linked document proposes to "simulate the execution of $M_x$ on $x$".

The repetition of the "$x$" is why it's called "diagonal".

Consider $$ \begin{array}{cccc} \text{Execute $M_1$ on $1$.} & \text{Execute $M_2$ on $1$.} & \text{Execute $M_3$ on $1$.} & \cdots\cdots \\ \text{Execute $M_1$ on $2$.} & \text{Execute $M_2$ on $2$.} & \text{Execute $M_3$ on $2$.} & \cdots\cdots \\ \text{Execute $M_1$ on $3$.} & \text{Execute $M_2$ on $3$.} & \text{Execute $M_3$ on $3$.} & \cdots\cdots \\ \vdots & \vdots & \vdots & \ddots \end{array} $$ Abbreviated: $$ \begin{array}{cccc} (1,1) & (2,1) & (3,1) & \cdots \\ (1,2) & (2,2) & (3,2) & \cdots \\ (1,3) & (2,3) & (3,3) & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{array} $$ The proof is telling you to do the things on the diagonal of this array.

share|cite|improve this answer
Very vivid and helpful, but Carls answer is somewhat more comprehensive. Thats why I chose it as accepted answer. – user1494080 Feb 1 '14 at 15:21

The idea does in fact comes from Cantor's Diagonal Argument. Recall how that argument works, if $f_n$ is a sequence of binary sequences then defining $f(n)=1-f_n(n)$ ensures that for every $n$, $f\neq f_n$.

Now given a class of functions (of any sort) with a common domain, if we can enumerate them using their domain, then defining $f(x)=f_x(x)+[\ldots]$ assures us that $f$ is not in that class of functions (where $\ldots$ is some reasonable and permitted operation, like adding $1$ or so).

Let me quote the second paragraph of Section $3.5$:

For concreteness, let us say that "diagonalization" is any technique that relies upon the following properties of Turing machines:

  1. The existence of an effective representations of Turing machines by strings.
  2. The ability of one TM to simulate any other without much overhead in running time or space.

This really just says that there is a way to encode Turing machines into strings of integers, and equally a natural number, and there is a Turing machine which takes an input of two numbers, decodes (if possible) the first one into a Turing machine, and simulate that machine when given the second number as an input.

So in fact we can think of Turing machines as natural numbers, and therefore we can index and input Turing machines to other Turing machines. So the above idea of diagonalization works. (Of course, since this topic is more about complexity of runtime you have to worry about the overheads, but as the second point in the excerpt says, that this is not a real worry.)

share|cite|improve this answer
Just one more question: How can we enumerate different functions using their (common) domain? – user1494080 Feb 1 '14 at 15:18
Think about the case of the natural numbers. Given a countable set of functions from $\Bbb N$ to $\Bbb N$. Can you enumerate them with their domain ($\Bbb N$)? – Asaf Karagila Feb 1 '14 at 15:23
I'm not quite sure. First, I don't exactly know what you mean by "enumerating using the domain". Second, I see no pattern how to enumerate all functions (like x, x^6, 4^x, ceil(log(x)) and so on) from IN to IN. – user1494080 Feb 1 '14 at 15:44
Enumeration does not mean that there is a pattern. It means that there is a function. Functions are not formulas. They are just sets of ordered pairs which satisfy certain properties. Also, note that we don't want to enumerate all the functions, just some countable class of them. – Asaf Karagila Feb 1 '14 at 15:46
For Turing machines, as the text and my answer both say, we can in fact find a canonical way of writing all the Turing machines in a sequence (which may not be injective, so some machines will appear more than once). This is one of the powers of Turing machine, that they can be used to enumerate themselves (again, if we think about Turing machines as functions from the natural numbers to the natural numbers). – Asaf Karagila Feb 1 '14 at 15:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.