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 , 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
3/23/2020
5
𝐃𝐅𝐀 𝐂𝐅𝐆
𝐓𝐌
decidable decidable
?
𝐃𝐅𝐀 𝐂𝐅𝐆
𝐓𝐌
decidable decidable
?
𝐃𝐅𝐀 𝐂𝐅𝐆
𝐓𝐌
decidable ? CS332 ‐ Theory of Computation
?
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 Proof:
A simplifying assumption: Every string in encoding of some Turing machine
∗ is the ∗
Set of all Turing machines:
Set of all languages over :
∗
There are more languages than there are TM deciders!
3/23/2020 CS332 ‐ Theory of Computation 7
all subsets of =
An existential proof
Theorem: There exists an unrecognizable language over Proof:
A simplifying assumption: Every string in encoding of some Turing machine
∗ is the ∗
Set of all Turing machines:
Set of all languages over :
∗
There are more languages than there are TM recognizers! 3/23/2020 CS332 ‐ Theory of Computation 8
all subsets of =
…
An explicit undecidable language
TM 𝑀
𝑀 𝑀 𝑀 𝑀
3/23/2020
CS332 ‐ Theory of Computation 9
…
An explicit undecidable language
TM𝑀 𝑀𝑀 ? 𝑀𝑀 ? 𝑀𝑀 ? 𝑀𝑀 ?
𝐷 𝐷 ?
𝑀 𝑀 𝑀 𝑀
Y N Y Y … NNYY
𝐷
3/23/2020
CS332 ‐ Theory of Computation 10
YYYN NNYN
Suppose decides
An explicit undecidable language
Theorem:
is undecidable
Proof: Suppose for contradiction, that
decides
Corollary:
is undecidable
3/23/2020 CS332 ‐ Theory of Computation
11
A more useful undecidable language
Theorem: is undecidable
But first: is Turing‐recognizable
The following “universal TM” recognizes
On input :
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
Theorem: is undecidable
Proof: Assume for the sake of contradiction that TM decides :
Idea: Show that can be used to decide the (undecidable) language ‐‐ a contradiction.
3/23/2020 CS332 ‐ Theory of Computation 14
A more useful undecidable language
Suppose decides
Consider the following TM . On input where is a TM:
1. Run
2. If
on input
accepts, accept. If rejects, reject.
Claim:
decides
3/23/2020
CS332 ‐ Theory of Computation 15
…but this language is undecidable
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
Theorem: is undecidable
Proof: Assume for the sake of contradiction that TM decides :
Idea: Show that can be used to decide the (undecidable) language ‐‐ a contradiction.
“A reduction from to ” 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 subroutine
as a
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
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/23/2020 CS332 ‐ Theory of Computation 22
Two uses of reductions
Negative uses: If reduces to and is undecidable, then is also undecidable
𝐴 𝑀,𝑤 𝑀 is a TM that accepts input 𝑤 Suppose 𝐻 decides 𝐴
Consider the following TM 𝐷.
On input 𝑀 where 𝑀 is a TM:
1. Run𝐻oninput 𝑀, 𝑀
2. If 𝐻 accepts, accept. If 𝐻 rejects, reject.
Claim: 𝐷 decides
𝑆𝐴 𝑀 𝑀 is a TM that accepts on input 𝑀
3/23/2020 CS332 ‐ Theory of Computation
23
Two uses of reductions
Negative uses: If reduces to and is undecidable, then is also undecidable
Proof template:
1. 2.
Suppose to the contrary that is decidable
3.
But is undecidable. Contradiction!
Using as a subroutine, construct an algorithm deciding
3/23/2020 CS332 ‐ Theory of Computation 24
Halting Problem
for
On input 1. Run 2. If
3. If
4. If
. We construct a decider for as follows: :
3/23/2020
CS332 ‐ Theory of Computation
is undecidable
Proof: Suppose for contradiction that there exists a decider
Theorem:
on input
rejects, reject
accepts, simulate on
accepts, accept. Otherwise, reject This is a reduction from
to 25
Empty language testing for TMs
Theorem: is undecidable
Proof: Suppose for contradiction that there exists a decider for . We construct a decider for as follows:
On input 1. Run
:
on input ???
3/23/2020
CS332 ‐ Theory of Computation
26
This is a reduction from to
Empty language testing for TMs
Theorem: is undecidable
Proof: Suppose for contradiction that there exists a decider for . We construct a decider for as follows:
On input :
1. Construct a TM as follows:
2. Run 3. If
on input
, accept. Otherwise, reject
3/23/2020
CS332 ‐ Theory of Computation
This is a reduction from
to 27