PowerPoint Presentation
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/9/2021 CS332 – Theory of Computation 2
Uncountability of the reals
Theorem: The real interval (0, 1) is uncountable.
Proof: Assume for the sake of contradiction it were
countable, and let 𝑓𝑓:ℕ → (0,1) be a bijection
3/10/2021 CS332 – Theory of Computation 3
Construct 𝑏𝑏 ∈ (0,1) which does not appear in this table:
𝑏𝑏 = 0. 𝑏𝑏1𝑏𝑏2𝑏𝑏3… where 𝑏𝑏𝑛𝑛 ≠ 𝑑𝑑𝑛𝑛𝑛𝑛 (digit 𝑛𝑛 of 𝑓𝑓(𝑛𝑛))
There is no 𝑛𝑛 for which 𝑓𝑓 𝑛𝑛 = 𝑏𝑏, which contradicts the
assumption that 𝑓𝑓 is onto
𝑛𝑛 𝑓𝑓(𝑛𝑛)
1 0 .𝑑𝑑1
1 𝑑𝑑2
1 𝑑𝑑3
1 𝑑𝑑4
1 𝑑𝑑5
1 …
2 0 .𝑑𝑑1
2 𝑑𝑑2
2 𝑑𝑑3
2 𝑑𝑑4
2 𝑑𝑑5
2 …
3 0 .𝑑𝑑1
3 𝑑𝑑2
3 𝑑𝑑3
3 𝑑𝑑4
3 𝑑𝑑5
3 …
4 0 .𝑑𝑑1
4 𝑑𝑑2
4 𝑑𝑑3
4 𝑑𝑑4
4 𝑑𝑑5
4 …
5 0 .𝑑𝑑1
5 𝑑𝑑2
5 𝑑𝑑3
5 𝑑𝑑4
5 𝑑𝑑5
5 …
Uncountability of the reals
A concrete example of the contradiction construction:
3/9/2021 CS332 – Theory of Computation 4
Construct 𝑏𝑏 ∈ (0,1) which does not appear in this table
𝑏𝑏 = 0. 𝑏𝑏1𝑏𝑏2𝑏𝑏3… where 𝑏𝑏𝑛𝑛 ≠ 𝑑𝑑𝑛𝑛𝑛𝑛 (digit 𝑛𝑛 of 𝑓𝑓(𝑛𝑛))
𝑛𝑛 𝑓𝑓(𝑛𝑛)
1 0 . 8 6 7 5 3 0 9 …
2 0 . 1 4 1 5 9 2 6 …
3 0 . 7 1 8 2 8 1 8 …
4 0 . 4 4 4 4 4 4 4 …
5 0 . 1 3 3 7 1 3 3 …
Diagonalization
This process of constructing a counterexample by
“contradicting the diagonal” is called diagonalization
3/9/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 𝑏𝑏 = 0. 𝑏𝑏1𝑏𝑏2𝑏𝑏3… 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/9/2021 CS332 – Theory of Computation 7
Diagonalization argument
Assume a correspondence 𝑓𝑓:𝑋𝑋 → 𝑃𝑃(𝑋𝑋)
3/9/2021 CS332 – Theory of Computation 8
𝑥𝑥
𝑥𝑥1
𝑥𝑥2
𝑥𝑥3
𝑥𝑥4
…
Diagonalization argument
Assume a correspondence 𝑓𝑓:𝑋𝑋 → 𝑃𝑃(𝑋𝑋)
3/9/2021 CS332 – Theory of Computation 9
𝑥𝑥 𝑥𝑥1 ∈ 𝑓𝑓(𝑥𝑥)? 𝑥𝑥2 ∈ 𝑓𝑓(𝑥𝑥)? 𝑥𝑥3 ∈ 𝑓𝑓(𝑥𝑥)? 𝑥𝑥4 ∈ 𝑓𝑓(𝑥𝑥)?
𝑥𝑥1 Y N Y Y
𝑥𝑥2 N N Y Y
𝑥𝑥3 Y Y Y N
𝑥𝑥4 N N Y N
…
…
Define 𝑆𝑆 by flipping the diagonal:
Put 𝑥𝑥𝑛𝑛 ∈ 𝑆𝑆 ⟺ 𝑥𝑥𝑛𝑛 ∉ 𝑓𝑓(𝑥𝑥𝑛𝑛)
Example
Let 𝑋𝑋 = 1, 2, 3 , 𝑃𝑃 𝑋𝑋 = {∅, 1 , 2 , 1,2 , 2,3 , {1,2,3}}
3/10/2021 CS332 – Theory of Computation 10
𝑥𝑥 1 ∈ 𝑓𝑓(𝑥𝑥)? 2 ∈ 𝑓𝑓(𝑥𝑥)? 3 ∈ 𝑓𝑓(𝑥𝑥)?
1
2
3
Ex. 𝑓𝑓 1 = 1, 2 , 𝑓𝑓 2 = ∅, 𝑓𝑓 3 = {2}
Construct 𝑆𝑆 = a) 1 c) {2, 3}
b) 1, 2, 3 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/9/2021 CS332 – Theory of Computation 11
Undecidable Languages
3/9/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 {0, 1}
Proof:
Set of all encodings of TM deciders: 𝑋𝑋 ⊆ {0, 1}∗
3/10/2021 CS332 – Theory of Computation 14
Set of all languages over {0, 1}:
a) 0, 1
b) 0, 1 ∗
c) 𝑃𝑃 0, 1 ∗ : The set of all subsets of 0, 1 ∗
d) 𝑃𝑃(𝑃𝑃 0, 1 ∗) : The set of all subsets of the set of all
subsets of 0, 1 ∗
An existential proof
Theorem: There exists an undecidable language over {0, 1}
Proof:
Set of all encodings of TM deciders: 𝑋𝑋 ⊆ {0, 1}∗
3/10/2021 CS332 – Theory of Computation 15
Set of all languages over {0, 1}: 𝑃𝑃 0, 1 ∗
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 {0, 1}
Proof:
Set of all encodings of TMs: 𝑋𝑋 ⊆ {0, 1}∗
3/10/2021 CS332 – Theory of Computation 16
Set of all languages over {0, 1}: 𝑃𝑃 0, 1 ∗
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 𝑀𝑀
𝑀𝑀1
𝑀𝑀2
𝑀𝑀3
𝑀𝑀4
…
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 𝑀𝑀 𝑀𝑀( 𝑀𝑀1 )? 𝑀𝑀( 𝑀𝑀2 )? 𝑀𝑀( 𝑀𝑀3 )? 𝑀𝑀( 𝑀𝑀4 )?
𝑀𝑀1 Y N Y Y
𝑀𝑀2 N N Y Y
𝑀𝑀3 Y Y Y N
𝑀𝑀4 N N Y N
…
…
𝑈𝑈𝑈𝑈 = 𝑀𝑀 𝑀𝑀 is a TM that does not accept on input 𝑀𝑀 }
Suppose 𝑈𝑈 decides 𝑈𝑈𝑈𝑈
𝑈𝑈( 𝑈𝑈 )?
𝑈𝑈
An explicit undecidable language
Theorem: 𝑈𝑈𝑈𝑈 = 𝑀𝑀 𝑀𝑀 is a TM that does not accept on
input 𝑀𝑀 } is undecidable
Proof: Suppose for contradiction, that TM 𝑈𝑈 decides 𝑈𝑈𝑈𝑈
3/10/2021 CS332 – Theory of Computation 20
A more useful undecidable language
𝐴𝐴TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that accepts input 𝑤𝑤}
Theorem: 𝐴𝐴TM is undecidable
Proof: Assume for the sake of contradiction that TM 𝐻𝐻
decides 𝐴𝐴TM:
𝐻𝐻 𝑀𝑀,𝑤𝑤 = �
accept if 𝑀𝑀 accepts 𝑤𝑤
reject if 𝑀𝑀 does not accept 𝑤𝑤
Idea: Show that 𝐻𝐻 can be used to decide the
(undecidable) language 𝑈𝑈𝑈𝑈 — a contradiction.
3/9/2021 CS332 – Theory of Computation 21
A more useful undecidable language
𝐴𝐴TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that accepts input 𝑤𝑤}
Proof (continued):
Suppose, for contradiction, that 𝐻𝐻 decides 𝐴𝐴TM
Consider the following TM 𝑈𝑈:
“On input 𝑀𝑀 where 𝑀𝑀 is a TM:
1. Run 𝐻𝐻 on input 𝑀𝑀, 𝑀𝑀
2. If 𝐻𝐻 accepts, reject. If 𝐻𝐻 rejects, accept.”
Claim: 𝑈𝑈 decides 𝑈𝑈𝑈𝑈 = 𝑀𝑀 TM 𝑀𝑀 does not accept 𝑀𝑀 }
…but this language is undecidable
3/9/2021 CS332 – Theory of Computation 22
Unrecognizable Languages
Theorem: A language 𝐿𝐿 is decidable if and only if 𝐿𝐿 and �𝐿𝐿
are both Turing-recognizable.
Proof:
3/9/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/9/2021 CS332 – Theory of Computation 25
regular
recognizable
decidable
BU CS 332 – Theory of Computation
How can we compare sizes of infinite sets?
Uncountability of the reals
Uncountability of the reals
Diagonalization
Structure of a diagonalization proof
A general theorem about set sizes
Diagonalization argument
Diagonalization argument
Example
A general theorem about set sizes
Undecidable Languages
Undecidability / Unrecognizability
An existential proof
An existential proof
An existential proof
“Almost all” languages are undecidable
An explicit undecidable language
An explicit undecidable language
An explicit undecidable language
A more useful undecidable language
A more useful undecidable language
Unrecognizable Languages
Unrecognizable Languages
Classes of Languages