CS代写 CS21 Decidability and Tractability

CS21 Decidability and Tractability
• undecidable problems
– computation histories
– surprising contrasts between

Copyright By PowCoder代写 加微信 powcoder

decidable/undecidable • Rice’s Theorem
• Post Correspondence Problem (skip)
• Beyond RE and co-RE
• Recursion Theorem
February 5, 2024 CS21 Lecture 14 2
Dec. and undec. problems
• two problems regarding Context-Free Grammars:
– does a CFG generate all strings:
ALLCFG ={:GisaCFGandL(G)=Σ*}
– CFG emptiness:
ECFG ={:GisaCFGandL(G)=Ø}
• Both decidable? both undecidable? one decidable?
February 5, 2024 CS21 Lecture 14 3
Dec. and undec. problems Theorem: ECFG is decidable.
– observation: for each nonterminal A, the set
SA ={w:A⇒*w}
is non-empty iff there is some rule:
and for all non-terminals B in string x, 𝑆! ≠ ∅
February 5, 2024 CS21 Lecture 14 4
Dec. and undec. problems
– on input
– mark all terminals in G
– repeat until no new non-terminals get marked:
• if there is a production A→x1x2x3…xk
• and each symbol x1, x2, …, xk has been marked • then mark A
– if S marked, reject (G ∉ ECFG), else accept (G ∈ ECFG).
– terminates? correct?
February 5, 2024 CS21 Lecture 14 5
Dec. and undec. problems Theorem: ALLCFG is undecidable.
– reduce from co-ATM (i.e. show co-ATM ≤m ALLCFG) – what should f() produce?
• produce CFG G that generates all strings that are not accepting computation histories of M on w
February 5, 2024 CS21 Lecture 14 6

Dec. and undec. problems
– build a NPDA, then convert to CFG
– want to accept strings not of this form,
#C1#C2#C3#…#Ck#
plus strings of this form but where
• C1 is not the start config. of M on input w, or
• Ck is not an accept. config. of M on input w, or • Ci does not yield in one step Ci+1 for some i
February 5, 2024 CS21 Lecture 14 7
Dec. and undec. problems
– our NPDA nondeterministically checks one of:
• C1 is not the start config. of M on input w, or
• Ck is not an accept. config. of M on input w, or • Ci does not yield in one step Ci+1 for some i
• input has fewer than two #’s
– details of first two?
– to check third condition:
• nondeterministically guess Ci starting position
• how to check that Ci doesn’t yield in 1 step Ci+1 ?
February 5, 2024 CS21 Lecture 14 8
Dec. and undec. problems
– checking:
• Ci does not yield in one step Ci+1 for some i – push Ci onto stack
– at #, start popping Ci and compare to Ci+1
• accept if mismatch away from head location, or • symbols around head changed in a way inconsistent with M’s transition function.
– is everything described possible with NPDA? February 5, 2024 CS21 Lecture 14 9
Dec. and undec. problems
– Problem: cannot compare Ci to Ci+1 – could prove in same way that proved
{ww: w ∈ Σ*} not context-free – recall that
{wwR: w ∈ Σ*} is context-free
– free to tweak construction of G in the reduction – solution: write computation history:
#C1#C2R #C3#C4R…#Ck#
February 5, 2024 CS21 Lecture 14 10
Dec. and undec. problems
– f() = equiv. to NPDA below:
on input x, accept if not of form:
#C1#C2R #C3#C4R…#Ck#
• accept if C1 is the not the start configuration for M on input w
• accept if check that Ci does not yield in one step Ci+1
• accept if Ck is not an accepting configuration for M
February 5, 2024
CS21 Lecture 14
• is f computable?
• YES maps to YES?
∈ co-ATM ⇒ f(M, w) ∈ ALLCFG
• NO maps to NO?
∉ co-ATM ⇒ f(M, w) ∉ ALLCFG
Rice’s Theorem
• We have seen that the following properties of TM’s are undecidable:
– TM accepts string w
– TM halts on input w
– TM accepts the empty language – TM accepts a regular language
• Can we describe a single generic reduction for all these proofs?
• Yes. Every property of TMs undecidable! February 5, 2024 CS21 Lecture 14 12

Rice’s Theorem
• A TM property is a language P for which – if L(M1) = L(M2) then ∈ P iff ∈ P
• TM property P is nontrivial if –thereexistsaTMM1 forwhich∈P,and –thereexistsaTMM2 forwhich∉P.
Rice’s Theorem: Every nontrivial TM property is undecidable.
February 5, 2024 CS21 Lecture 14 13
Rice’s Theorem
• The setup:
–letTØ beaTMforwhichL(TØ)=Ø
• technicality: if ∈ P then work with property co-P instead of P.
• conclude co-P undecidable; therefore P undec. due to closure under complement
– so, WLOG, assume ∉ P –non-trivialityensuresexistenceofTMM1 such
that ∈ P
February 5, 2024 CS21 Lecture 14 14
Rice’s Theorem
– reduce from ATM (i.e. show ATM ≤m P)
– what should f() produce?
– f() = described below:
on input x,
• accept iff M accepts w
and M1 accepts x
(intersection of two RE languages)
February 5, 2024
CS21 Lecture 14
• f computable?
• YES maps to YES?
∈ ATM ⇒ L(f(M, w)) = L(M1) ⇒ f(M, w) ∈ P
Rice’s Theorem
– reduce from ATM (i.e. show ATM ≤m P)
– what should f() produce?
– f() = described below:
• NO maps to NO?
on input x,
• accept iff M accepts w
and M1 accepts x
(intersection of two RE languages)
February 5, 2024 CS21 Lecture 14
∉ ATM⇒
L(f(M, w)) = L(TØ) ⇒ f(M, w) ∉ P

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com