Microsoft PowerPoint – CS332-Lec13-ann
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
Theorem: 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: is
decidable
Proof: The following TM decides
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
Theorem: is decidable
Proof: The following TM decides
On input , where are DFAs:
1. Construct a DFA that recognizes the symmetric
difference
2. Run the decider for on and return its output
3/8/2021 CS332 ‐ Theory of Computation 5
Symmetric Difference
3/8/2021 CS332 ‐ Theory of Computation 6
Meta‐Computational Languages
3/8/2021 CS332 ‐ Theory of Computation 7
The Universal Turing Machine
Theorem: is Turing‐recognizable
The following “universal TM” recognizes
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
Why is the Universal TM not a decider for ?
The following “universal TM” 𝑈 recognizes 𝐴
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 machineM,
then U will compute the same sequence asM.”
‐ 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
is Turing‐recognizable
…but it turns out (and ) 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:
b) The even numbers:
c) The positive powers of 2:
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
•
•
•
•
•
•
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
Stage 2) List all pairs such that
…
Stage ) List all pairs such that
…
• Argue that every element of appears in the list
Ex: Any will be listed in stage
• 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
• ∗
•
•
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 is uncountable.
Proof: Assume for the sake of contradiction it were
countable, and let be a bijection
3/8/2021 CS332 ‐ Theory of Computation 22
Construct which does not appear in this table
– contradiction!
… where (digit of )
𝑛 𝑓 𝑛
1 0 .𝑑 𝑑 𝑑 𝑑 𝑑 …
2 0 .𝑑 𝑑 𝑑 𝑑 𝑑 …
3 0 .𝑑 𝑑 𝑑 𝑑 𝑑 …
4 0 .𝑑 𝑑 𝑑 𝑑 𝑑 …
5 0 .𝑑 𝑑 𝑑 𝑑 𝑑 …