BU CS 332 – Theory of Computation
Lecture 15:
• Undecidable and Unrecognizable Languages
Reading:
Sipser Ch 4.2, 5.1
• Reductions
Mark Bun March 23, 2020
How can we compare sizes of infinite sets?
Definition: Two sets have the same size if there is a correspondence (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/23/2020 CS332 – Theory of Computation 2
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: Use diagonalization to construct a set 𝑆𝑆 ∈ 𝑃𝑃(𝑋𝑋) that cannot be the output 𝑓𝑓(𝑥𝑥) for any 𝑥𝑥 ∈ 𝑋𝑋
3/23/2020 CS332 – Theory of Computation 3
Undecidable Languages
3/23/2020 CS332 – Theory of Computation 4
Problems in language theory
𝑨𝑨𝐃𝐃𝐃𝐃𝐃𝐃 𝑨𝑨𝐂𝐂𝐃𝐃𝐂𝐂
𝑨𝑨𝐓𝐓𝐓𝐓
𝑬𝑬𝑬𝑬 𝐃𝐃𝐃𝐃𝐃𝐃 𝐂𝐂𝐃𝐃𝐂𝐂
𝑬𝑬? 𝐓𝐓𝐓𝐓
decidable decidable
decidable decidable ? 𝑬𝑬𝑬𝑬 𝑬𝑬𝑬𝑬 𝑬𝑬𝑬𝑬
𝐃𝐃𝐃𝐃𝐃𝐃 𝐂𝐂𝐃𝐃𝐂𝐂 𝐓𝐓𝐓𝐓
3/23/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/23/2020 CS332 – Theory of Computation 6
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/23/2020 CS332 – Theory of Computation 7
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/23/2020 CS332 – Theory of Computation 8
An explicit undecidable language
TM 𝑀𝑀
𝑀𝑀1 𝑀𝑀2 𝑀𝑀3 𝑀𝑀4
3/23/2020
CS332 – Theory of Computation 9
…
An explicit undecidable language
TM𝑀𝑀 𝑀𝑀(𝑀𝑀1 )? 𝑀𝑀(𝑀𝑀2 )? 𝑀𝑀(𝑀𝑀3 )? 𝑀𝑀(𝑀𝑀4 )?
𝑀𝑀1 𝑀𝑀2 𝑀𝑀3 𝑀𝑀4
𝐷𝐷( 𝐷𝐷 )? YNYY
N
Y
N
N
Y
N
Y
Y
Y
Y
N
N
…
𝐷𝐷
𝐿𝐿 = 𝑀𝑀 𝑀𝑀isaTMthatdoesnotacceptoninput 𝑀𝑀 }
Suppose 𝐷𝐷 decides 𝐿𝐿
3/23/2020 CS332 – Theory of Computation 10
…
An explicit undecidable language
Theorem: 𝐿𝐿 = 𝑀𝑀 𝑀𝑀 is a TM that does not accept on input 𝑀𝑀 } is undecidable
Proof: Suppose for contradiction, that 𝐷𝐷 decides 𝐿𝐿
Corollary: 𝑆𝑆𝑆𝑆TM = 𝐿𝐿� = 𝑀𝑀 𝑀𝑀 is a TM that accepts on
input 𝑀𝑀 } is undecidable
3/23/2020 CS332 – Theory of Computation 11
A more useful 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/23/2020 CS332 – Theory of Computation 12
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/23/2020 CS332 – Theory of Computation 13
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 𝑆𝑆𝑆𝑆TM — a contradiction.
3/23/2020 CS332 – Theory of Computation 14
A more useful 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, accept. If 𝐻𝐻 rejects, reject.
Claim: 𝐷𝐷 decides
𝑆𝑆𝑆𝑆TM = 𝑀𝑀 𝑀𝑀isaTMthatacceptsoninput 𝑀𝑀 }
…but this language is undecidable
3/23/2020 CS332 – Theory of Computation 15
Unrecognizable Languages � Theorem: A language 𝐿𝐿 is decidable if and only if 𝐿𝐿 and 𝐿𝐿
are both Turing-recognizable.
Proof:
3/23/2020 CS332 – Theory of Computation 16
Classes of Languages
recognizable
decidable context free
regular
3/23/2020 CS332 – Theory of Computation 17
Reductions
3/23/2020 CS332 – Theory of Computation 18
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 𝑆𝑆𝑆𝑆TM — a contradiction.
“A reduction from 𝑆𝑆𝑆𝑆TM to 𝑆𝑆TM”
3/23/2020 CS332 – Theory of Computation 19
Scientists vs. Engineers
A computer scientist and an engineer are stranded on a desert island. They find two palm trees with one coconut on each. The engineer climbs a tree, picks a coconut and eats.
The computer scientist climbs the second tree, picks a coconut, climbs down, climbs up the first tree and places it there, declaring success.
“Now we’ve reduced the problem to one we’ve already solved.”
3/23/2020 CS332 – Theory of Computation 20
Reductions
A reduction from problem 𝑆𝑆 to problem 𝐵𝐵 is an algorithm for problem 𝑆𝑆 which uses an algorithm for problem 𝐵𝐵 as a subroutine
If such a reduction exists, we say “𝑆𝑆 reduces to 𝐵𝐵”
3/23/2020 CS332 – Theory of Computation 21
Two uses of reductions
Positive uses: If 𝑆𝑆 reduces to 𝐵𝐵 and 𝐵𝐵 is decidable, then 𝑆𝑆 is also decidable
𝐸𝐸𝑄𝑄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/23/2020 CS332 – Theory of Computation 22
Two uses of reductions
Negative uses: If 𝑆𝑆 reduces to 𝐵𝐵 and 𝑆𝑆 is undecidable, then 𝐵𝐵 is also undecidable
𝑆𝑆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, accept. If 𝐻𝐻 rejects, reject.
Claim: 𝐷𝐷 decides
𝑆𝑆𝑆𝑆TM = 𝑀𝑀 𝑀𝑀isaTMthatacceptsoninput 𝑀𝑀 }
3/23/2020 CS332 – Theory of Computation 23
Two uses of reductions
Negative uses: If 𝑆𝑆 reduces to 𝐵𝐵 and 𝑆𝑆 is undecidable, then 𝐵𝐵 is also undecidable
Suppose to the contrary that 𝐵𝐵 is decidable Using 𝐵𝐵 as a subroutine, construct an algorithm
Proof template:
1. 2.
3.
deciding 𝑆𝑆
But 𝑆𝑆 is undecidable. Contradiction!
3/23/2020 CS332 – Theory of Computation 24
Halting Problem
𝐻𝐻𝑆𝑆𝐿𝐿𝐻𝐻TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀isaTMthathaltsoninput𝑤𝑤} Theorem: 𝐻𝐻𝑆𝑆𝐿𝐿𝐻𝐻TM is undecidable
Proof: Suppose for contradiction that there exists a decider 𝐻𝐻 for 𝐻𝐻𝑆𝑆𝐿𝐿𝐻𝐻TM. We construct a decider for 𝑆𝑆TM as follows:
Oninput 𝑀𝑀,𝑤𝑤:
1. Run 𝐻𝐻 on input 𝑀𝑀,𝑤𝑤
2. 3. 4.
If 𝐻𝐻 rejects, reject
If 𝐻𝐻 accepts, simulate 𝑀𝑀 on 𝑤𝑤
If 𝑀𝑀 accepts, accept. Otherwise, reject
This is a reduction from 𝑆𝑆TM to 𝐻𝐻𝑆𝑆𝐿𝐿𝐻𝐻TM 3/23/2020 CS332 – Theory of Computation 25
Empty language testing for TMs
𝐸𝐸TM = 𝑀𝑀 𝑀𝑀isaTMand𝐿𝐿 𝑀𝑀 =∅} Theorem: 𝐸𝐸TM is undecidable
Proof: Suppose for contradiction that there exists a decider 𝑅𝑅 for 𝐸𝐸TM. We construct a decider for 𝑆𝑆TM as follows:
Oninput 𝑀𝑀,𝑤𝑤:
1. Run 𝑅𝑅 on input ???
This is a reduction from 𝑆𝑆TM to 𝐸𝐸TM 3/23/2020 CS332 – Theory of Computation 26
Empty language testing for TMs
𝐸𝐸TM = 𝑀𝑀 𝑀𝑀isaTMand𝐿𝐿 𝑀𝑀 =∅} Theorem: 𝐸𝐸TM is undecidable
Proof: Suppose for contradiction that there exists a decider 𝑅𝑅 for 𝐸𝐸TM. We construct a decider for 𝑆𝑆TM as follows:
Oninput 𝑀𝑀,𝑤𝑤:
1. Construct a TM 𝑀𝑀𝑀 as follows:
2.Run𝑅𝑅oninput 𝑀𝑀′
3. If 𝑅𝑅 , accept. Otherwise, reject
This is a reduction from 𝑆𝑆TM to 𝐸𝐸TM 3/23/2020 CS332 – Theory of Computation 27
Context-free language testing for TMs
𝐶𝐶𝐶𝐶𝐿𝐿TM = 𝑀𝑀 𝑀𝑀isaTMand𝐿𝐿 𝑀𝑀 iscontext−free} Theorem: 𝐶𝐶𝐶𝐶𝐿𝐿TM is undecidable
Proof: Suppose for contradiction that there exists a decider 𝑅𝑅 for 𝐶𝐶𝐶𝐶𝐿𝐿TM. We construct a decider for 𝑆𝑆TM as follows:
Oninput 𝑀𝑀,𝑤𝑤:
1. Construct a TM 𝑀𝑀𝑀 as follows:
2.Run𝑅𝑅oninput 𝑀𝑀′
3. If 𝑅𝑅 accepts, accept. Otherwise, reject
This is a reduction from 𝑆𝑆TM to 𝐶𝐶𝐶𝐶𝐿𝐿TM 3/23/2020 CS332 – Theory of Computation 28
Context-free language testing for TMs
𝐶𝐶𝐶𝐶𝐿𝐿TM = 𝑀𝑀 𝑀𝑀isaTMand𝐿𝐿 𝑀𝑀 iscontext−free} Theorem: 𝐶𝐶𝐶𝐶𝐿𝐿TM is undecidable
Proof: Suppose for contradiction that there exists a decider 𝑅𝑅 for 𝐶𝐶𝐶𝐶𝐿𝐿TM. We construct a decider for 𝑆𝑆TM as follows:
Oninput 𝑀𝑀,𝑤𝑤:
1. Construct a TM 𝑀𝑀𝑀 as follows:
𝑀𝑀𝑀 = “On input 𝑥𝑥,
1.If𝑥𝑥∈ 0𝑛𝑛1𝑛𝑛2𝑛𝑛 𝑛𝑛≥0},accept 2. Run TM 𝑀𝑀 on input 𝑤𝑤
3. If 𝑀𝑀 accepts, accept.”
2.Run𝑅𝑅oninput 𝑀𝑀′
3. If 𝑅𝑅 accepts, accept. Otherwise, reject
This is a reduction from 𝑆𝑆TM to 𝐶𝐶𝐶𝐶𝐿𝐿TM 3/23/2020 CS332 – Theory of Computation 29