BU CS 332 – Theory of Computation
Lecture 14:
• Countability
• Undecidable Languages
Reading: Sipser Ch 4.2
Mark Bun March 18, 2020
Last Time
𝑨𝑨𝐃𝐃𝐃𝐃𝐃𝐃 𝑨𝑨𝐂𝐂𝐃𝐃𝐂𝐂
𝑬𝑬𝑬𝑬 𝐃𝐃𝐃𝐃𝐃𝐃 𝐂𝐂𝐃𝐃𝐂𝐂
decidable decidable
𝑬𝑬𝑬𝑬
decidable decidable
𝐃𝐃𝐃𝐃𝐃𝐃
decidable
3/17/2020
CS332 – Theory of Computation
2
One more decidable language (Sipser 4.10)
Theorem: 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼DFA =
𝐷𝐷 𝐷𝐷 is a DFA that accepts infinitely many strings}
Lemma: Let 𝐷𝐷 be a DFA with 𝑛𝑛 states. Then 𝐷𝐷 accepts infinitely many strings if and only if 𝐷𝐷 accepts some string of length ≥ 𝑛𝑛.
is decidable
3/18/2020 CS332 – Theory of Computation 3
One more decidable language (Sipser 4.10)
Theorem: 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼DFA =
𝐷𝐷 𝐷𝐷 is a DFA that accepts infinitely many strings}
is decidable
Proof: The following TM decides 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼 :
DFA On input 𝐷𝐷 , where 𝐷𝐷 is a DFA with 𝑛𝑛 states:
1. 2. 3.
Let 𝐴𝐴 be a DFA recognizing all strings of length ≥ 𝑛𝑛 Let 𝐵𝐵 be a DFA recognizing 𝐿𝐿(𝐴𝐴) ∩ 𝐿𝐿(𝐷𝐷)
Run the decider for 𝐼𝐼DFA on input 𝐵𝐵 . Accept if it rejects, and reject if it accepts.
3/18/2020 CS332 – Theory of Computation
4
Problems in Language Theory
𝑨𝑨𝐃𝐃𝐃𝐃𝐃𝐃 𝑨𝑨𝐂𝐂𝐃𝐃𝐂𝐂
𝑨𝑨𝐓𝐓𝐓𝐓
𝑬𝑬𝑬𝑬 𝐃𝐃𝐃𝐃𝐃𝐃 𝐂𝐂𝐃𝐃𝐂𝐂
𝑬𝑬? 𝐓𝐓𝐓𝐓
decidable decidable
decidable decidable ? 𝑬𝑬𝑬𝑬 𝑬𝑬𝑬𝑬 𝑬𝑬𝑬𝑬
𝐃𝐃𝐃𝐃𝐃𝐃 𝐂𝐂𝐃𝐃𝐂𝐂 𝐓𝐓𝐓𝐓
3/18/2020
decidable ? ? CS332 – Theory of Computation 5
Undecidability
These natural computational questions about computational models are undecidable
I.e., computers cannot solve these problems no matter how much time they are given
3/18/2020 CS332 – Theory of Computation 6
Countability and Diagonalizaiton
3/17/2020 CS332 – Theory of Computation 7
Set Theory Review
A function 𝑓𝑓:𝐴𝐴 → 𝐵𝐵 is
• 1-to-1 (injective) if 𝑓𝑓 𝑎𝑎 ≠
𝑓𝑓 𝑎𝑎𝑎 forall𝑎𝑎 ≠𝑎𝑎𝑎
• onto (surjective) if for all 𝑏𝑏 ∈ 𝐵𝐵, there exists 𝑎𝑎 ∈ 𝐴𝐴 such that 𝑓𝑓𝑎𝑎=𝑏𝑏
• a correspondence (bijective) if it is 1-to-1 and onto, i.e., every 𝑏𝑏 ∈ 𝐵𝐵 has a unique 𝑎𝑎 ∈ 𝐴𝐴 with 𝑓𝑓𝑎𝑎=𝑏𝑏
3/17/2020 CS332 – Theory of Computation 8
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 N, the set of natural numbers
3/17/2020 CS332 – Theory of Computation 9
Examples of countable sets
•∅
• 0,1
• 0, 1, 2, … 8675309
• 𝐼𝐼 = {2,4,6,8,…}
• 𝑆𝑆𝑆𝑆𝑆𝑆𝐴𝐴𝑆𝑆𝐼𝐼𝑆𝑆 = 1,4,9,16,25,… • 𝑃𝑃𝑃𝑃𝑃𝑃𝑃 = 1,2,4,8,16,32,…
𝐼𝐼 = 𝑆𝑆𝑆𝑆𝑆𝑆𝐴𝐴𝑆𝑆𝐼𝐼𝑆𝑆 = 𝑃𝑃𝑃𝑃𝑃𝑃𝑃 =|N|
3/17/2020 CS332 – Theory of Computation 10
How to show that N × N is countable? (1,1) (2,1) (3,1) (4,1) 5,1 …
(1,2) (2,2) (3,2) (4,2) (5,2) (1,3) (2,3) (3,3) (4,3) (5,3) (1,4) (2,4) (3,4) (4,4) (5,4) (1,5) (2,5) (3,5) (4,5) (5,5)
…
3/17/2020 CS332 – Theory of Computation
11
More examples of countable sets
• {0,1} ∗
• 𝑀𝑀 𝑀𝑀 is a Turing machine} • Q = {rational numbers}
So what isn’t countable?
3/18/2020 CS332 – Theory of Computation 12
Cantor’s Diagonalization Method
Georg Cantor 1845-1918
• Invented set theory
• Defined countability, uncountability,
cardinal and ordinal numbers, …
Some praise for his work:
“Scientific charlatan…renegade…corruptor of youth” –L. Kronecker
“Set theory is wrong…utter nonsense…laughable” –L. Wittgenstein
Sylvester Medal, Royal Society, 1904
3/18/2020
CS332 – Theory of Computation 13
Uncountability of the reals
Theorem: The real interval (0, 1) is uncountable. Proof: Assume for the sake of contradiction it were
countable, and let 𝑓𝑓: N → (0,1) be a correspondence
𝑛𝑛 𝑓𝑓(𝑛𝑛)
1 0 . 𝑑𝑑 1 1 𝑑𝑑 21 𝑑𝑑 31 𝑑𝑑 41 𝑑𝑑 51 … 0 . 𝑑𝑑 12 𝑑𝑑 2 2 𝑑𝑑 32 𝑑𝑑 42 𝑑𝑑 52 … 0 . 𝑑𝑑 13 𝑑𝑑 23 𝑑𝑑 3 3 𝑑𝑑 43 𝑑𝑑 53 … 4 0 . 𝑑𝑑 14 𝑑𝑑 24 𝑑𝑑 34 𝑑𝑑 4 4 𝑑𝑑 54 …
2
3
Construct 𝑏𝑏 ∈ (0,1) which does not appear in this table – contradiction!
0 . 𝑑𝑑5 𝑑𝑑5 𝑑𝑑5 𝑑𝑑5 𝑑𝑑5 … 12345
5
𝑏𝑏=0.𝑑𝑑 𝑑𝑑 𝑑𝑑 …where𝑑𝑑 ≠digit𝑖𝑖of𝑓𝑓(𝑖𝑖) 123 𝑖𝑖
3/18/2020 CS332 – Theory of Computation 14
Uncountability of the reals
𝑛𝑛 𝑓𝑓(𝑛𝑛)
1 0.8675309… 0.1415926… 0.7182818… 0.4444444… 0.1337133…
A concrete example:
2
3
4
5
Construct 𝑏𝑏 ∈ (0,1) which does not appear in this table – contradiction!
𝑏𝑏=0.𝑑𝑑 𝑑𝑑 𝑑𝑑 …where𝑑𝑑 ≠digit𝑖𝑖of𝑓𝑓(𝑖𝑖) 123 𝑖𝑖
3/18/2020 CS332 – Theory of Computation 15
Diagonalization
This process of constructing a counterexample by “contradicting the diagonal” is called diagonalization
3/18/2020 CS332 – Theory of Computation 16
What if we try to do this with the rationals?
What happens if we try to use this argument to show that Q ∩ (0,1) [rational numbers in (0,1)] is uncountable?
Let 𝑓𝑓: N → Q ∩ (0,1) be a correspondence 𝑛𝑛 𝑓𝑓(𝑛𝑛)
1 0.8678678… 0.1414141… 0.7182718… 4 0.4444444… 5 0.1337133…
2
3
Construct 𝑏𝑏 ∈ (0,1) which does not appear in this table
𝑏𝑏 = 0. 𝑑𝑑1𝑑𝑑2𝑑𝑑3… where 𝑑𝑑𝑖𝑖 ≠ digit 𝑖𝑖 of 𝑓𝑓(𝑖𝑖)
3/18/2020 CS332 – Theory of Computation 17
A general theorem about set sizes
Theorem: Let 𝑋𝑋 be a set. Then the power set 𝑃𝑃(𝑋𝑋) does not have the same size as 𝑋𝑋.
Proof: Assume for the sake of contradiction that there is a correspondence 𝑓𝑓: 𝑋𝑋 → 𝑃𝑃(𝑋𝑋)
Goal: Construct a set 𝑆𝑆 ∈ 𝑃𝑃(𝑋𝑋) that cannot be the output 𝑓𝑓(𝑥𝑥) for any 𝑥𝑥 ∈ 𝑋𝑋
3/18/2020 CS332 – Theory of Computation 18
Diagonalization argument
Assume a correspondence 𝑓𝑓: 𝑋𝑋 → 𝑃𝑃(𝑋𝑋)
𝑥𝑥𝑥𝑥 𝑥𝑥1 𝑥𝑥2 𝑥𝑥3
4
3/18/2020
CS332 – Theory of Computation 19
…
Diagonalization argument
Assume a correspondence 𝑓𝑓: 𝑋𝑋 → 𝑃𝑃(𝑋𝑋)
𝑥𝑥 𝑥𝑥1 ∈𝑓𝑓(𝑥𝑥)? 𝑥𝑥2 ∈𝑓𝑓(𝑥𝑥)? 𝑥𝑥3 ∈𝑓𝑓(𝑥𝑥)? 𝑥𝑥4 ∈𝑓𝑓(𝑥𝑥)? …
𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4
YNYY
N
Y
N
N
Y
N
Y
Y
Y
Y
N
N
Define 𝑆𝑆 by flipping the diagonal:
Put 𝑥𝑥𝑖𝑖 ∈𝑆𝑆 ⟺ 𝑥𝑥𝑖𝑖 ∉𝑓𝑓(𝑥𝑥𝑖𝑖)
3/18/2020 CS332 – Theory of Computation 20
…
Example
Let𝑋𝑋= 1,2,3,𝑃𝑃𝑋𝑋 ={∅, 1, 2, 1,2, 2,3,{1,2,3}} Ex.𝑓𝑓1 = 1,2,𝑓𝑓2 =∅, 𝑓𝑓3 ={2}
𝑥𝑥 1∈𝑓𝑓(𝑥𝑥)? 2 ∈𝑓𝑓(𝑥𝑥)? 3 ∈𝑓𝑓(𝑥𝑥)? 123
…
Construct 𝑆𝑆 =
3/18/2020 CS332 – Theory of Computation 21
…
A general theorem about set sizes
Theorem: Let 𝑋𝑋 be a set. Then the power set 𝑃𝑃(𝑋𝑋) does not have the same size as 𝑋𝑋.
Proof: Assume for the sake of contradiction that there is a correspondence 𝑓𝑓: 𝑋𝑋 → 𝑃𝑃(𝑋𝑋)
Construct a set 𝑆𝑆 ∈ 𝑃𝑃(𝑋𝑋) that cannot be the output 𝑓𝑓(𝑥𝑥)
for any 𝑥𝑥 ∈ 𝑋𝑋:
If 𝑆𝑆 = 𝑓𝑓(𝑦𝑦) for some 𝑦𝑦 ∈ 𝑋𝑋,
𝑆𝑆 = 𝑥𝑥 ∈ 𝑋𝑋 𝑥𝑥 ∉ 𝑓𝑓(𝑥𝑥)}
then 𝑦𝑦 ∈ 𝑆𝑆 if and only if 𝑦𝑦 ∉ 𝑆𝑆
3/18/2020 CS332 – Theory of Computation 22
Undecidable Languages
3/18/2020 CS332 – Theory of Computation 23
An Existential Proof
Theorem: There exists an undecidable language over {0, 1} Proof:
A simplifying assumption: Every string in {0, 1}∗ is the encoding 𝑀𝑀 of some Turing machine 𝑀𝑀
Set of all Turing machines: 𝑋𝑋 = {0, 1}∗
Set of all languages over {0, 1} = all subsets of {0, 1}∗
There are more languages than there are TM deciders!
3/18/2020 CS332 – Theory of Computation 24
= 𝑃𝑃(𝑋𝑋)
An Existential Proof
Theorem: There exists an unrecognizable language over {0, 1} Proof:
A simplifying assumption: Every string in {0, 1}∗ is the encoding 𝑀𝑀 of some Turing machine 𝑀𝑀
Set of all Turing machines: 𝑋𝑋 = {0, 1}∗
Set of all languages over {0, 1} = all subsets of {0, 1}∗
There are more languages than there are TM recognizers! 3/18/2020 CS332 – Theory of Computation 25
= 𝑃𝑃(𝑋𝑋)
A Specific Undecidable Language
𝐴𝐴TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that accepts input 𝑤𝑤} Theorem: 𝐴𝐴TM is undecidable
But first: 𝐴𝐴TM is Turing-recognizable
The following “universal TM” 𝑆𝑆 recognizes 𝐴𝐴TM
Oninput 𝑀𝑀,𝑤𝑤:
1. Simulate running 𝑀𝑀 on input 𝑤𝑤
2. If 𝑀𝑀 accepts, accept. If 𝑀𝑀 rejects, reject.
3/18/2020 CS332 – Theory of Computation 26
More on the Universal TM
“It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D [“standard description”] of some computing machine M, then U will compute the same sequence as M.”
– Turing, “On Computable Numbers…” 1936 • Foreshadowed general-purpose programmable computers
• No need for specialized hardware: Virtual machines as software
Harvard architecture: von Neumann architecture: Separate instruction and data pathways Programs can be treated as data
3/18/2020 CS332 – Theory of Computation 27
A Specific 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 𝑤𝑤
Diagonalization: Use 𝐻𝐻 to check what 𝑀𝑀 when given as input its own description…and do the opposite
3/18/2020 CS332 – Theory of Computation 28
A Specific Undecidable Language
𝐴𝐴TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that accepts input 𝑤𝑤} Suppose 𝐻𝐻 decides 𝐴𝐴TM
Consider the following TM 𝐷𝐷. On input 𝑀𝑀 where 𝑀𝑀 is a TM:
1. Run𝐻𝐻oninput 𝑀𝑀, 𝑀𝑀
2. If 𝐻𝐻 accepts, reject. If 𝐻𝐻 rejects, accept.
Question: What does 𝐷𝐷 do on input 𝐷𝐷 ?
3/18/2020 CS332 – Theory of Computation 29
How is this diagonalization?
TM 𝑀𝑀
𝑀𝑀1 𝑀𝑀2 𝑀𝑀3 𝑀𝑀4
3/18/2020
CS332 – Theory of Computation 30
…
How is this diagonalization?
TM𝑀𝑀 𝑀𝑀(𝑀𝑀1 )? 𝑀𝑀(𝑀𝑀2 )? 𝑀𝑀(𝑀𝑀3 )? 𝑀𝑀(𝑀𝑀4 )? …
YNYY
𝑀𝑀1 𝑀𝑀2 𝑀𝑀3 𝑀𝑀4
N
Y
N
N
Y
N
Y
Y
Y
Y
N
N
𝐷𝐷 accepts input 𝑀𝑀𝑖𝑖 ⟺ 𝑀𝑀𝑖𝑖 does not accept input 𝑀𝑀𝑖𝑖 3/18/2020 CS332 – Theory of Computation 31
…
How is this diagonalization?
TM𝑀𝑀 𝑀𝑀(𝑀𝑀1 )? 𝑀𝑀(𝑀𝑀2 )? 𝑀𝑀(𝑀𝑀3 )? 𝑀𝑀(𝑀𝑀4 )? 𝐷𝐷(𝐷𝐷)?
𝑀𝑀1 𝑀𝑀2 𝑀𝑀3 𝑀𝑀4
YNYY
N
Y
N
N
Y
N
Y
Y
Y
Y
N
N
…
𝐷𝐷
𝐷𝐷 accepts input 𝑀𝑀𝑖𝑖 ⟺ 𝑀𝑀𝑖𝑖 does not accept input 𝑀𝑀𝑖𝑖
3/18/2020 CS332 – Theory of Computation 32
…
3/18/2020 CS332 – Theory of Computation 33
𝐴𝐴TM = 𝑀𝑀,𝑤𝑤
𝑀𝑀 is a TM that accepts input 𝑤𝑤} 1. Simulate running 𝑀𝑀 on input 𝑤𝑤
Oninput 𝑀𝑀,𝑤𝑤:
2. If 𝑀𝑀 accepts, accept. If 𝑀𝑀 rejects, reject.
3/18/2020 CS332 – Theory of Computation 34