Microsoft PowerPoint – CS332-Lec14
BU CS 332 – Theory of Computation
Lecture 14:
• More on Diagonalization
• Undecidability
Reading:
Sipser Ch 4.2
Mark Bun
March 10, 2021
How can we compare sizes of infinite sets?
Definition: Two sets have the same size if there is a
bijection between them
A set is countable if
• it is a finite set, or
• it has the same size as , the set of natural numbers
3/10/2021 CS332 ‐ Theory of Computation 2
Uncountability of the reals
Theorem: The real interval is uncountable.
Proof: Assume for the sake of contradiction it were
countable, and let be a bijection
3/10/2021 CS332 ‐ Theory of Computation 3
Construct which does not appear in this table:
… where (digit of )
There is no for which , which contradicts the
assumption that is onto
𝑛 𝑓 𝑛
1 0 .𝑑 𝑑 𝑑 𝑑 𝑑 …
2 0 .𝑑 𝑑 𝑑 𝑑 𝑑 …
3 0 .𝑑 𝑑 𝑑 𝑑 𝑑 …
4 0 .𝑑 𝑑 𝑑 𝑑 𝑑 …
5 0 .𝑑 𝑑 𝑑 𝑑 𝑑 …
Uncountability of the reals
A concrete example of the contradiction construction:
3/10/2021 CS332 ‐ Theory of Computation 4
Construct which does not appear in this table
… where (digit of )
1
2
3
4
5
Diagonalization
This process of constructing a counterexample by
“contradicting the diagonal” is called diagonalization
3/10/2021 CS332 ‐ Theory of Computation 5
Structure of a diagonalization proof
Say you want to show that a set is uncountable
1) Assume, for the sake of contradiction, that is
countable with bijection
2) “Flip the diagonal” to construct an element such
that for every
3) Conclude that is not onto, contradicting assumption
that is a bijection
3/10/2021 CS332 ‐ Theory of Computation 6
Ex: Let … where
(where is digit of )
A general theorem about set sizes
Theorem: Let be any set. Then the power set does
not have the same size as .
Proof: Assume for the sake of contradiction that there is a
bijection
Goal: Construct a set that cannot be the output
for any
3/10/2021 CS332 ‐ Theory of Computation 7
Diagonalization argument
Assume a correspondence
3/10/2021 CS332 ‐ Theory of Computation 8
𝑥
𝑥
𝑥
𝑥
𝑥
…
Diagonalization argument
Assume a correspondence
3/10/2021 CS332 ‐ Theory of Computation 9
𝑥 𝑥 ∈ 𝑓 𝑥 ? 𝑥 ∈ 𝑓 𝑥 ? 𝑥 ∈ 𝑓 𝑥 ? 𝑥 ∈ 𝑓 𝑥 ?
𝑥 Y N Y Y
𝑥 N N Y Y
𝑥 Y Y Y N
𝑥 N N Y N
…
…
Define by flipping the diagonal:
Put
Example
Let
3/10/2021 CS332 ‐ Theory of Computation 10
𝑥 1 ∈ 𝑓 𝑥 ? 2 ∈ 𝑓 𝑥 ? 3 ∈ 𝑓 𝑥 ?
1
2
3
Ex.
Construct a) c)
b) d)
A general theorem about set sizes
Theorem: Let be any set. Then the power set does
not have the same size as .
Proof: Assume for the sake of contradiction that there is a
bijection
Construct a set that cannot be the output
for any :
If for some ,
then if and only if
3/10/2021 CS332 ‐ Theory of Computation 11
Undecidable Languages
3/10/2021 CS332 ‐ Theory of Computation 12
Undecidability / Unrecognizability
Definition: A language is undecidable if there is no TM
deciding
Definition: A language is unrecognizable if there is no
TM recognizing
3/10/2021 CS332 ‐ Theory of Computation 13
An existential proof
Theorem: There exists an undecidable language over
Proof:
Set of all encodings of TM deciders: ∗
3/10/2021 CS332 ‐ Theory of Computation 14
Set of all languages over :
a)
b) ∗
c) ∗ : The set of all subsets of ∗
d) ∗ : The set of all subsets of the set of all
subsets of ∗
An existential proof
Theorem: There exists an undecidable language over
Proof:
Set of all encodings of TM deciders: ∗
3/10/2021 CS332 ‐ Theory of Computation 15
Set of all languages over : ∗
There are more languages than there are TM deciders!
There must be an undecidable language
An existential proof
Theorem: There exists an unrecognizable language over
Proof:
Set of all encodings of TMs: ∗
3/10/2021 CS332 ‐ Theory of Computation 16
Set of all languages over : ∗
There are more languages than there are TM deciders!
There must be an unrecognizable language
“Almost all” languages are undecidable
So how about we find one?
3/10/2021 CS332 ‐ Theory of Computation 17
An explicit undecidable language
3/10/2021 CS332 ‐ Theory of Computation 18
TM 𝑀
𝑀
𝑀
𝑀
𝑀
…
Why is it possible to enumerate all TMs like this?
a) The set of all TM deciders is finite
b) The set of all TM deciders is countably infinite
c) The set of all TM deciders is uncountable
An explicit undecidable language
3/10/2021 CS332 ‐ Theory of Computation 19
TM 𝑀 𝑀 𝑀 ? 𝑀 𝑀 ? 𝑀 𝑀 ? 𝑀 𝑀 ?
𝑀 Y N Y Y
𝑀 N N Y Y
𝑀 Y Y Y N
𝑀 N N Y N
…
…
Suppose decides
𝐷 𝐷 ?
𝐷
An explicit undecidable language
Theorem:
is undecidable
Proof: Suppose for contradiction, that TM decides
3/10/2021 CS332 ‐ Theory of Computation 20
A more useful undecidable language
Theorem: is undecidable
Proof: Assume for the sake of contradiction that TM
decides :
Idea: Show that can be used to decide the
(undecidable) language ‐‐ a contradiction.
3/10/2021 CS332 ‐ Theory of Computation 21
A more useful undecidable language
Proof (continued):
Suppose, for contradiction, that decides
Consider the following TM :
“On input where is a TM:
1. Run on input
2. If accepts, reject. If rejects, accept.”
Claim: decides
…but this language is undecidable
3/10/2021 CS332 ‐ Theory of Computation 22
Unrecognizable Languages
Theorem: A language is decidable if and only if and
are both Turing‐recognizable.
Proof:
3/10/2021 CS332 ‐ Theory of Computation 23
Unrecognizable Languages
Theorem: A language is decidable if and only if and
are both Turing‐recognizable.
Proof:
3/10/2021 CS332 ‐ Theory of Computation 24
Classes of Languages
3/10/2021 CS332 ‐ Theory of Computation 25
regular
recognizable
decidable