CS代考计算机代写 algorithm BU CS 332 – Theory of Computation

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