CS作业代写 CS21 Decidability and Tractability

CS21 Decidability and Tractability
Lecture 15 February 7, 2024
• Post Correspondence Problem (skip) • Beyond RE and co-RE
• Recursion Theorem

Copyright By PowCoder代写 加微信 powcoder

• On to complexity…
February 7, 2024 CS21 Lecture 15 2
Post Correspondence Problem
• many undecidable problems unrelated to TMs and automata
• classic example: Post Correspondence Problem
PCP = {<(x1, y1), (x2, y2), ..., (xk, yk)> :
xi, yi ∈ Σ* and there exists (a1, a2, …, an) for
which xa1xa2…xan = ya1ya2…yan}
February 7, 2024 CS21 Lecture 15 3
Post Correspondence Problem
PCP = {<(x1, y1), (x2, y2), ..., (xk, yk)> :
xi, yi ∈ Σ* and there exists (a1, a2, …, an) for
y3 “tiles”
February 7, 2024
x2 x1 x5 x2 x1 x3 x4 x4
y2 y1 y5 y2 y1 y3 y4 y4 x2x1x5x2x1x3x4x4 = y2y1y5y2y1y3y4y4
which xa1xa2…xan = ya1ya2…yan}
CS21 Lecture 15
Post Correspondence Problem Theorem: PCP is undecidable.
– reduce from ATM (i.e. show ATM ≤m PCP) – two step reduction makes it easier
– first, show ATM ≤m MPCP
(MPCP = “modified PCP”)
– next, show MPCP ≤m PCP
February 7, 2024 CS21 Lecture 15 5
Post Correspondence Problem
MPCP = {<(x1, y1), (x2, y2), ..., (xk, yk)> : xi, yi ∈ Σ* and there exists (a1, a2, …, an) for
which x1xa1xa2…xan = y1ya1ya2…yan}
Proof of MPCP ≤m PCP:
– notation: for a string u = u1u2u3…um
• ⋆u means the string
• u⋆ means the string
•⋆u⋆ meansthestring
February 7, 2024 CS21 Lecture 15 6
⋆u1⋆u2⋆u3⋆u4…⋆um u1⋆u2⋆u3⋆u4…⋆um⋆
⋆u1⋆u2⋆u3⋆u4…⋆um⋆

Post Correspondence Problem
Proof of MPCP ≤m PCP:
– given an instance (x1, y1), …, (xk, yk) of MPCP – produce an instance of PCP:
(⋆x1, ⋆y1⋆) , (⋆x1, y1⋆), (⋆x2, y2⋆), …, (⋆xk, yk⋆), (⋆ □,□) – YES maps to YES?
• given a match in original MPCP instance, can produce a match in the new PCP instance
– NO maps to NO?
• given a match in the new PCP instance, can produce a match in the original MPCP instance
February 7, 2024 CS21 Lecture 15 7
Post Correspondence Problem – YES maps to YES?
• given a match in original MPCP instance, can produce a match in the new PCP instance
x1 x4 x5 x2 x1 x3 x4 x4 y1 y4 y5 y2 y1 y3 y4 y4
⋆x1 ⋆x4 ⋆x5 ⋆x2 ⋆x1 ⋆x3 ⋆x4 ⋆x4 ⋆□ ⋆y1⋆ Y4⋆ y5⋆ y2⋆ y1⋆ y3⋆ y4⋆ y4⋆ □
February 7, 2024 CS21 Lecture 15 8
Post Correspondence Problem
– NO maps to NO?
• given a match in the new PCP instance, can produce a match in the original MPCP instance
⋆x1 ⋆x4 ⋆x5 ⋆x2 ⋆x1 ⋆x3 ⋆x4 ⋆x4 ⋆□ ⋆y1⋆ Y4⋆ y5⋆ y2⋆ y1⋆ y3⋆ y4⋆ y4⋆ □
x1 x4 x5 x2 x1 x3 x4 x4 ⋆ symbols must align
y1 y4 y5 y2 y1 y3 y4 y4 February 7, 2024 CS21 Lecture 15
can’t match unless start with this tile
can only appear at the end
Post Correspondence Problem
Theorem: PCP is undecidable. Proof:
– show ATM ≤m MPCP
MPCP = {<(x1, y1), (x2, y2), ..., (xk, yk)> : xi, yi ∈ Σ* and there exists (a1, a2, …, an) for
which x1xa1xa2…xan = y1ya1ya2…yan}
– show MPCP ≤m PCP
February 7, 2024 CS21 Lecture 15 10
Post Correspondence Problem
Proof of ATM ≤m MPCP:
– given instance of ATM:
– idea: a match will record an accepting computation history for M on input w
– start tile records starting configuration:
• add tile (#, #q0w1w2w3…wn#)
February 7, 2024 CS21 Lecture 15 11
# #q0w1w2…wn#
Post Correspondence Problem
??…?= ???
– tiles for head motions to the right:
• foralla,b∈Γandallq,r∈Qwithq≠qreject, if δ(q, a) = (r, b, R), add tile (qa, br)
– tiles for head motions to the left:
• foralla,b,c∈Γandallq,r∈Qwithq≠qreject,
if δ(q, a) = (r, b, L), add tile (cqa, rcb)
# q0w1w2…wn#
February 7, 2024 CS21 Lecture 15
#C1# #C1#C2#

Post Correspondence Problem
??…?= ???
– tiles for copying (not near head)
# q0w1w2…wn#
• foralla∈Γ,addtile(a,a)
– tiles for copying # marker
• add tile (#, #)
– tiles for copying # marker and adding _ to end
• add tile (#, _#)
February 7, 2024 CS21 Lecture 15
#C1# #C1#C2#
Post Correspondence Problem
– tiles for deleting symbols to left of qaccept
• for all a ∈ Γ, add tile (aqaccept, qaccept)
February 7, 2024 CS21 Lecture 15 14
# #uaqacceptv#
#uaqacceptv# #uaqacceptv#uqacceptv#
aqaccept qaccept
Post Correspondence Problem
– tiles for deleting symbols to right of qaccept
• for all a ∈ Γ, add tile (qaccepta, qaccept)
February 7, 2024 CS21 Lecture 15 15
# #qacceptav#
#qacceptav# #qacceptav#qacceptv#
qaccepta qaccept
Post Correspondence Problem
– tiles for completing the match
• for all a ∈ Γ, add tile (qaccept##, #)
February 7, 2024 CS21 Lecture 15 16
# #qaccept#
#qaccept## #qaccept##
qaccept## #
Post Correspondence Problem
– YES maps to YES?
• by construction, if M accepts w, there is a way to assemble the tiles to achieve this match:
where #C1#C2#C3#…#Cm# is an accepting computation history
– NO maps to NO?
• sketch: at any step if the “intended” next tile is not used, then it is impossible to recover and produce a match in the end (case analysis)
February 7, 2024 CS21 Lecture 15 17
#C1#C2#C3#…#Cm# #C1#C2#C3#…#Cm#
Post Correspondence Problem We have proved:
Theorem: PCP is undecidable.
by showing:
– ATM ≤m MPCP – MPCP ≤m PCP
– conclude ATM ≤m PCP
February 7, 2024 CS21 Lecture 15 18

Beyond RE and co-RE
• We saw (by a counting argument) that
Therefore, not
there is some language that is neither RE
Therefore, not inRE
• We will prove this for a natural language:
EQTM = { : L(M1) = L(M2)}
– ATM is undecidable, but RE
– co-ATM is undecidable, but coRE
February 7, 2024 CS21 Lecture 15 19
Beyond RE and co-RE Theorem: EQTM is neither RE nor coRE.
• reduce from co-ATM (i.e. show co-ATM ≤m EQTM) • what should f() produce?
– not co-RE:
• reduce from ATM (i.e. show ATM ≤m EQTM)
• what should f() produce?
February 7, 2024 CS21 Lecture 15 20
Beyond RE and co-RE
Proof (ATM ≤m EQTM)
– f() = described below:
TM M1: on input x,
TM M2: on input x,
• simulate M on input w • accept if M accepts w
February 7, 2024
•YES maps to YES?
∈ATM ⇒L(M1)=Σ* and L(M2) = Σ*
⇒ f() ∈ EQTM
•NOmapstoNO?
∉ATM ⇒L(M1)=Σ* and L(M2) = Ø
⇒ f() ∉ EQTM
CS21 Lecture 15 21
Beyond RE and co-RE
Proof (co-ATM ≤m EQTM)
– f() = described below:
TM M1: on input x,
TM M2: on input x,
• simulate M on input w • accept if M accepts w
February 7, 2024
•YES maps to YES?
∈ co-ATM
⇒L(M1) = Ø and L(M2) = Ø ⇒ f() ∈ EQTM
•NOmapstoNO?
∉ co-ATM
⇒L(M1) = Ø and L(M2) = Σ* ⇒ f() ∉ EQTM
CS21 Lecture 15 22
{anbn : n ≥ 0 }
regular languages
context free languages
February 7, 2024
decidable co-RE
{anbncn : n ≥ 0 }
CS21 Lecture 15
some language
all languages
The Recursion Theorem
• A very useful, and non-obvious, capability of Turing Machines:
– in the course of computation, can print out a description of itself!
• how is this possible?
– an example of a program that prints out self:
Print two copies of the following, the 2nd one in quotes: “Print two copies of the following, the 2nd one in quotes:”
February 7, 2024 CS21 Lecture 15 24

The Recursion Theorem
• Why is this useful?
• Example: slick proof that ATM undecidable
– assume TM M decides ATM
– construct machine M’ as follows:
on input x,
• obtain own description
• run M on input
• if M rejects, accept; if M accepts, reject.
February 7, 2024
if M’ on input x:
• accepts, then M rejects , but then M’ does not accept!
• rejects, then M accepts
, but then M’ accepts!
CS21 Lecture 15 25
The Recursion Theorem
• Lemma: there is a computable function q:Σ* → Σ*
such that q(w) is a description of a TM Pw that prints out w and then halts.
– on input w, construct TM Pw that has w hard-
coded into it; output
February 7, 2024 CS21 Lecture 15 26
The Recursion Theorem
• Warm-up: produce a TM SELF that prints out its own description.
• Two parts:
• output a description of B • pass control to B.
• prepend a description of A • done
February 7, 2024 CS21 Lecture 15 27
The Recursion Theorem
• output a description of B • pass control to B.
• prepend a description of A • done
Note: = q()
Recall: q(w) is a description of a TM Pw that prints out w and then halts.
*combine with description on tape to produce a complete TM
February 7, 2024 CS21 Lecture 15 28
• read contents of tape
•applyqtoit
• prepend* result to tape
A • output
The Recursion Theorem
Note: = q()
Recall: q(w) is a description of a TM Pw that prints out w and then halts.
– watch closely as TM AB runs:
– A runs. Tape contents:
– B runs. Tape contents: q() = – AB is our desired machine SELF.
February 7, 2024 CS21 Lecture 15 29
• read contents of tape
•applyqtoit
• prepend result to tape
A • output
The Recursion Theorem
• Lemma: there is a computable function q:Σ* → Σ*
such that q(w) is a description of a TM Pw that prints out w and then halts.
– on input w, construct TM Pw that has w hard-
coded into it; output
February 7, 2024 CS21 Lecture 15 30