Theory of Computation
The Diagonalization Method
The University of Iowa, Department of Computer Science
Copyright Teodor Rus. These lecture notes have been developed by Teodor Rus using the book: Michael Sipser, Introduction to the Theory of Computation (second
edition), published by Thomson Course Technology 2006. They are copyrighted materials and may not be used in other course settings outside of the University of Iowa in
their current form or modiﬁed form without the express written permission of one of the copyright holders. During this course, students are prohibited from selling notes to or
being paid for taking notes by any person or commercial ﬁrm without the express written permission of one of the copyright holders.
Computation Theory. Copyrights Teodor Rus – p.1/54Decidability of TM Language
ForM a Turing machine andw a string,
A =hM,wiM is a TM that acceptsw
Computation Theory. Copyrights Teodor Rus – p.2/54Solution
Theorem 4.11: A is recognizable but not
A recognizer ofA is the following TM called
the Turing Universal MachineU:
U = “On inputhM,wi, whereM is a TM andw is a string:
1. SimulatesM onw;
2. IfM ever enters its accept state, accept;
ifM ever enters its reject state, reject ".
Note: U is a universal TM because it simulates any other TM
from its description.
Computation Theory. Copyrights Teodor Rus – p.3/54Facts
1. So far we have tackled only solvable (decidable) problems;
2. Theorem 4.11 states thatA is unsolvable (undecidable);
3. SinceA is undecidable, to solve this problem we need to
expand our problem solving methodology by a new method for
Computation Theory. Copyrights Teodor Rus – p.4/54Diagonalization
The proof of undecidability of the halting
problem uses Georg Cantor (1873) technique
Cantor’s problem was to measure the size of
The size of ﬁnite sets is measured by
counting the number of their elements;
Question: can we measure the size of an inﬁnite
set by counting the number of its elements?
Computation Theory. Copyrights Teodor Rus – p.5/54Fact
The size of inﬁnite sets cannot be measured by
counting their elements because this procedure
does not halt
Computation Theory. Copyrights Teodor Rus – p.6/54Example Inﬁnite Sets
The set of strings over0,1 is an inﬁnite set;
The setN of natural number is an inﬁnite set;
Both of them are larger than any ﬁnite set.
How can we compare them?
Design a mappingf :N →0,1 by:
1. f(0) =ǫ;
2. f(n) =x∈0,1 x =n.
Computation Theory. Copyrights Teodor Rus – p.7/54Fact
f actually mapsN onP(0,1 ).
Since x = y for any x,y ∈ f(n), is an equivalence relation on
0,1 and we can considerf :N →0,1 /.
Computation Theory. Copyrights Teodor Rus – p.8/54Cantor’s Solution
Two ﬁnite sets have the same size if their
elements can be paired;
Since this method do not rely on counting
elements it can be used for both ﬁnite and
Computation Theory. Copyrights Teodor Rus – p.9/546
Consider two sets,A andB andf :A→B a
f is one-to-one if it never maps two different elements ofA into
the same element ofB, i.e.,∀a,b∈A(a =b⇒f(a) =f(b));
f is onto if it hits every element ofB, i.e.,∀b∈B,∃a∈A such
f is called a correspondence if it is both one-to-one and onto.
Note: a correspondence is a mechanism that al-
lows us to pair elements of two sets.
Computation Theory. Copyrights Teodor Rus – p.10/54Set Size Comparison
Two setsA andB have the same size if there is a
Computation Theory. Copyrights Teodor Rus – p.11/54Example Correspondences
LetN be the set of natural numbers,N =1,2,3,...
and letE be the set of even natural numbers,E =2,4,6,...;
Intuitively one may believe thatsize(N)size(E). However,
using Cantor method we can show thatN andE have the same
size by constructing a correspondencef :N →E;
The correspondencef is deﬁned byf(n) = 2n, Figure 1.
Computation Theory. Copyrights Teodor Rus – p.12/546
Figure 1: sizeof(N) =sizeof(E)
1. ∀n ,n ∈N,n =n ,f(n ) = 2n ,f(n ) = 2n i.e.,
1 2 1 2 1 1 2 2
f(n ) =f(n );
2. ∀n∈E,n = 2m,m∈N , i.e.,n =f(m).
Hence,f is a correspondence and thussizeof(N) =sizeof(E).
Computation Theory. Copyrights Teodor Rus – p.13/54Deﬁnition 4.12
A set is countable if either it is ﬁnite or it has the
same size asN .
Computation Theory. Copyrights Teodor Rus – p.14/54A Complex Correspondence
LetQ be the set of positive rational numbers,
Q = m,n∈N.
Intuitively,Q seems to be much larger thanN ;
Yet we can show thatsizeof(Q) =sizeof(N)
by constructing the correspondence
c :N →Q shown in Figure 2.
Computation Theory. Copyrights Teodor Rus – p.15/54Correspondencec :Q↔N
1. PutN on two axes;
2. Linei contains all rational numbers that have
numeratori, i.e. ∈Qi∈N fixed,∀j ∈N;
3. Columnj contains all rational numbers that
have denominatorj, i.e. ∈Q∀i∈N,j ∈N fixed;
4. Number occurs ini-th line andj-th column.
Computation Theory. Copyrights Teodor Rus – p.16/54i
Turning i,j ∈N into a List
Bad idea: list ﬁrst elements of a line or a
Lines and columns are labeled byN , hence this would never end
Good idea (Cantor’s idea): use the diagonals:
1. First diagonal contains , i.e, ﬁrst element of the list is ;
2. Continue the list with the elements of the next diagonal: , ;
3. Continue this way skipping the elements that may generate
repetitions, such that would generate a copy of .
Computation Theory. Copyrights Teodor Rus – p.17/54The List of Rational Numbers
1 2 3 4 5
1 1 1 1 1
1 2 3 4 5
2 2 2 2 2
1 2 3 4 5
3 3 3 3 3
1 2 3 4 5
4 4 4 4 4
1 2 3 4 5
5 5 5 5 5
1 2 3 4 5
... ... ... ... ... ... ...
Figure 2: A correspondence ofN andQ
Computation Theory. Copyrights Teodor Rus – p.18/54Uncountable Sets
A set for which no correspondence withN can
be established is called uncountable.
Example of uncountable set:
The setR of real numbers is uncountable
Proof: Cantor proved thatR is uncountable using
the diagonalization method.
Computation Theory. Copyrights Teodor Rus – p.19/54Example Uncountable Set
Theorem 4.17;R is uncountable.
Proof: by contradiction using diagonalization.
We will show that no correspondence exist
Suppose that such a correspondence
f :N →R exits and deduce a contradiction
showing thatf fail to work properly.
We construct anx∈R that cannot be the
image of anyn∈N .
Computation Theory. Copyrights Teodor Rus – p.20/54