PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 13:
• Decidable Languages
• Universal TM
• Countability and
Diagonalization
Reading:
Sipser Ch 4.1, 4.2
Mark Bun
March 8, 2021
A “universal” algorithm for recognizing regular
languages
𝐴𝐴DFA = 𝐷𝐷,𝑤𝑤 DFA 𝐷𝐷 accepts 𝑤𝑤}
Theorem: 𝐴𝐴DFA is decidable
Proof: Define a 3-tape TM 𝑀𝑀 on input 𝐷𝐷,𝑤𝑤 :
1. Check if 𝐷𝐷,𝑤𝑤 is a valid encoding (reject if not)
2. Simulate 𝐷𝐷 on 𝑤𝑤, i.e.,
• Tape 2: Maintain 𝑤𝑤 and head location of 𝐷𝐷
• Tape 3: Maintain state of 𝐷𝐷, update according to 𝛿𝛿
3. Accept if 𝐷𝐷 ends in an accept state, reject otherwise
3/8/2021 CS332 – Theory of Computation 2
More Decidable Languages: Emptiness Testing
Theorem: 𝐸𝐸DFA = 𝐷𝐷 𝐷𝐷 is a DFA that recognizes ∅} is
decidable
Proof: The following TM decides 𝐸𝐸DFA
On input 𝐷𝐷 , where 𝐷𝐷 is a DFA with 𝑘𝑘 states:
1. Perform 𝑘𝑘 steps of breadth-first search on state
diagram of 𝐷𝐷 to determine if an accept state is
reachable from the start state
2. Reject if a DFA accept state is reachable; accept
otherwise
3/8/2021 CS332 – Theory of Computation 3
3/8/2021 CS332 – Theory of Computation 4
𝐸𝐸𝐷𝐷𝐷𝐷𝐷𝐷 Example
New Deciders from Old: Equality Testing
𝐸𝐸𝑄𝑄DFA = ⟨𝐷𝐷1,𝐷𝐷2⟩ 𝐷𝐷1,𝐷𝐷2 are DFAs and 𝐿𝐿(𝐷𝐷1) = 𝐿𝐿(𝐷𝐷2)}
Theorem: 𝐸𝐸𝑄𝑄DFA is decidable
Proof: The following TM decides 𝐸𝐸𝑄𝑄DFA
On input ⟨𝐷𝐷1,𝐷𝐷2⟩ , where 𝐷𝐷1,𝐷𝐷2 are DFAs:
1. Construct a DFA 𝐷𝐷 that recognizes the symmetric
difference 𝐿𝐿(𝐷𝐷1) △ 𝐿𝐿(𝐷𝐷2)
2. Run the decider for 𝐸𝐸DFA on 𝐷𝐷 and return its output
3/8/2021 CS332 – Theory of Computation 5
Symmetric Difference
𝐴𝐴 △ 𝐵𝐵 = 𝑤𝑤 𝑤𝑤 ∈ 𝐴𝐴 or 𝑤𝑤 ∈ 𝐵𝐵 but not both}
3/8/2021 CS332 – Theory of Computation 6
Meta-Computational Languages
𝐴𝐴DFA = 𝐷𝐷,𝑤𝑤 DFA 𝐷𝐷 accepts 𝑤𝑤}
𝐸𝐸DFA = 𝐷𝐷 DFA 𝐷𝐷 recognizes the empty language ∅}
𝐸𝐸𝑄𝑄DFA = 𝐷𝐷1,𝐷𝐷2 𝐷𝐷1 and 𝐷𝐷2 are DFAs, 𝐿𝐿 𝐷𝐷1 = 𝐿𝐿 𝐷𝐷2 }
3/8/2021 CS332 – Theory of Computation 7
𝐴𝐴TM = 𝑀𝑀,𝑤𝑤 TM 𝑀𝑀 accepts 𝑤𝑤}
𝐸𝐸TM = 𝑀𝑀 TM 𝑀𝑀 recognizes the empty language ∅}
𝐸𝐸𝑄𝑄TM = 𝑀𝑀1,𝑀𝑀2 𝑀𝑀1 and 𝑀𝑀2 are TMs, 𝐿𝐿 𝑀𝑀1 = 𝐿𝐿 𝑀𝑀2 }
The Universal Turing Machine
𝐴𝐴TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that accepts input 𝑤𝑤}
Theorem: 𝐴𝐴TM is Turing-recognizable
The following “universal TM” 𝑈𝑈 recognizes 𝐴𝐴TM
On input 𝑀𝑀,𝑤𝑤 :
1. Simulate running 𝑀𝑀 on input 𝑤𝑤
2. If 𝑀𝑀 accepts, accept. If 𝑀𝑀 rejects, reject.
3/8/2021 CS332 – Theory of Computation 8
Universal TM and 𝐴𝐴TM
Why is the Universal TM not a decider for 𝐴𝐴TM?
The following “universal TM” 𝑈𝑈 recognizes 𝐴𝐴TM
On input 𝑀𝑀,𝑤𝑤 :
1. Simulate running 𝑀𝑀 on input 𝑤𝑤
2. If 𝑀𝑀 accepts, accept. If 𝑀𝑀 rejects, reject.
a) It may reject inputs 〈𝑀𝑀,𝑤𝑤〉 where 𝑀𝑀 accepts 𝑤𝑤
b) It may accept inputs 〈𝑀𝑀,𝑤𝑤〉 where 𝑀𝑀 rejects 𝑤𝑤
c) It may loop on inputs 〈𝑀𝑀,𝑤𝑤〉 where 𝑀𝑀 loops on 𝑤𝑤
d) It may loop on inputs 〈𝑀𝑀,𝑤𝑤〉 where 𝑀𝑀 rejects 𝑤𝑤
3/8/2021 CS332 – Theory of Computation 9
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
3/8/2021 CS332 – Theory of Computation 10
Harvard architecture:
Separate instruction and data pathways
von Neumann architecture:
Programs can be treated as data
Undecidability
𝐴𝐴TM is Turing-recognizable
…but it turns out 𝐴𝐴TM (and 𝐸𝐸TM,𝐸𝐸𝑄𝑄TM) is undecidable
i.e., computers cannot solve these problems no matter
how much time they are given
3/8/2021 CS332 – Theory of Computation 11
Countability and
Diagonalizaiton
3/8/2021 CS332 – Theory of Computation 12
What’s your intuition?
Which of the following sets is the “biggest”?
a) The natural numbers: ℕ = {1, 2, 3, … }
b) The even numbers: 𝐸𝐸 = 2, 4, 6, …
c) The positive powers of 2: 𝑃𝑃𝑃𝑃𝑃𝑃𝑃 = {2, 4, 8, 16, … }
d) They all have the same size
3/8/2021 CS332 – Theory of Computation 13
Set Theory Review
A function 𝑓𝑓:𝐴𝐴 → 𝐵𝐵 is
• 1-to-1 (injective) if 𝑓𝑓 𝑎𝑎 ≠
𝑓𝑓 𝑎𝑎𝑎 for all 𝑎𝑎 ≠ 𝑎𝑎𝑎
• 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/8/2021 CS332 – Theory of Computation 14
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/8/2021 CS332 – Theory of Computation 15
Examples of countable sets
• ∅
• 0,1
• 0, 1, 2, … , 8675309
• 𝐸𝐸 = {2, 4, 6, 8, … }
• 𝑆𝑆𝑄𝑄𝑈𝑈𝐴𝐴𝑆𝑆𝐸𝐸𝑆𝑆 = 1, 4, 9, 16, 25, …
• 𝑃𝑃𝑃𝑃𝑃𝑃𝑃 = 2, 4, 8, 16, 32, …
𝐸𝐸 = 𝑆𝑆𝑄𝑄𝑈𝑈𝐴𝐴𝑆𝑆𝐸𝐸𝑆𝑆 = 𝑃𝑃𝑃𝑃𝑃𝑃𝑃 = |ℕ|
3/8/2021 CS332 – Theory of Computation 16
How to show that ℕ × ℕ is countable?
3/8/2021 CS332 – Theory of Computation 17
(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)
…
…
…
…
How to argue that a set 𝑆𝑆 is countable
• Describe how to “list” the elements of 𝑆𝑆, usually in stages:
Ex: Stage 1) List all pairs (𝑥𝑥,𝑦𝑦) such that 𝑥𝑥 + 𝑦𝑦 = 2
Stage 2) List all pairs (𝑥𝑥,𝑦𝑦) such that 𝑥𝑥 + 𝑦𝑦 = 3
…
Stage 𝑛𝑛) List all pairs (𝑥𝑥,𝑦𝑦) such that 𝑥𝑥 + 𝑦𝑦 = 𝑛𝑛 + 1
…
• Argue that every element of 𝑆𝑆 appears in the list
Ex: Any 𝑥𝑥,𝑦𝑦 ∈ ℕ × ℕ will be listed in stage 𝑥𝑥 + 𝑦𝑦 − 1
• Define the bijection 𝑓𝑓: ℕ → 𝑆𝑆 by 𝑓𝑓 𝑛𝑛 = the 𝑛𝑛’th element
in this list (ignoring duplicates if needed)
3/8/2021 CS332 – Theory of Computation 18
Subsets of countable sets
If 𝐴𝐴 and 𝐵𝐵 are sets with 𝐴𝐴 ⊆ 𝐵𝐵 (𝐴𝐴 is a subset of 𝐵𝐵), which
of the following statements are true?
a) If 𝐴𝐴 is countable, then 𝐵𝐵 is countable
b) If 𝐵𝐵 is countable, then 𝐴𝐴 is countable
c) Both are true
d) Neither is true
3/8/2021 CS332 – Theory of Computation 19
More examples of countable sets
• {0,1} ∗
• 𝑀𝑀 𝑀𝑀 is a Turing machine}
• ℚ = {rational numbers}
So what isn’t countable?
3/8/2021 CS332 – Theory of Computation 20
Cantor’s Diagonalization Method
3/8/2021 CS332 – Theory of Computation 21
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
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/8/2021 CS332 – Theory of Computation 22
Construct 𝑏𝑏 ∈ (0,1) which does not appear in this table
– contradiction!
𝑏𝑏 = 0. 𝑏𝑏1𝑏𝑏2𝑏𝑏3… where 𝑏𝑏𝑖𝑖 ≠ 𝑑𝑑𝑖𝑖
𝑖𝑖 (digit 𝑖𝑖 of 𝑓𝑓(𝑖𝑖))
𝑛𝑛 𝑓𝑓(𝑛𝑛)
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/8/2021 CS332 – Theory of Computation 23
Construct 𝑏𝑏 ∈ (0,1) which does not appear in this table
– contradiction!
𝑏𝑏 = 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/8/2021 CS332 – Theory of Computation 24
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/8/2021 CS332 – Theory of Computation 25
Diagonalization argument
Assume a correspondence 𝑓𝑓:𝑋𝑋 → 𝑃𝑃(𝑋𝑋)
3/8/2021 CS332 – Theory of Computation 26
𝑥𝑥
𝑥𝑥1
𝑥𝑥2
𝑥𝑥3
𝑥𝑥4
…
Diagonalization argument
Assume a correspondence 𝑓𝑓:𝑋𝑋 → 𝑃𝑃(𝑋𝑋)
3/8/2021 CS332 – Theory of Computation 27
𝑥𝑥 𝑥𝑥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/8/2021 CS332 – Theory of Computation 28
𝑥𝑥 1 ∈ 𝑓𝑓(𝑥𝑥)? 2 ∈ 𝑓𝑓(𝑥𝑥)? 3 ∈ 𝑓𝑓(𝑥𝑥)?
1
2
3
Ex. 𝑓𝑓 1 = 1, 2 , 𝑓𝑓 2 = ∅, 𝑓𝑓 3 = {2}
Construct 𝑆𝑆 =
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/8/2021 CS332 – Theory of Computation 29
BU CS 332 – Theory of Computation
A “universal” algorithm for recognizing regular languages
More Decidable Languages: Emptiness Testing
𝐸 𝐷𝐹𝐴 Example
New Deciders from Old: Equality Testing
Symmetric Difference
Meta-Computational Languages
The Universal Turing Machine
Universal TM and 𝐴 TM
More on the Universal TM
Undecidability
Countability and Diagonalizaiton
What’s your intuition?
Set Theory Review
How can we compare sizes of infinite sets?
Examples of countable sets
How to show that ℕ×ℕ is countable?
How to argue that a set 𝑆 is countable
Subsets of countable sets
More examples of countable sets
Cantor’s Diagonalization Method
Uncountability of the reals
Uncountability of the reals
Diagonalization
A general theorem about set sizes
Diagonalization argument
Diagonalization argument
Example
A general theorem about set sizes