CS代考 CS21 Decidability and Tractability

CS21 Decidability and Tractability
Lecture 13 February 2, 2024
• reductions
• many-one reductions • undecidable problems

Copyright By PowCoder代写 加微信 powcoder

– computation histories
– surprising contrasts between
decidable/undecidable • Rice’s Theorem
February 2, 2024 CS21 Lecture 13 2
Definition of reduction
• Can you reduce co-HALT to HALT?
• We know that HALT is RE
• Does this show that co-HALT is RE?
– recall, we showed co-HALT is not RE
• our current notion of reduction cannot distinguish complements
February 2, 2024 CS21 Lecture 13 3
Definition of reduction
• More refined notion of reduction:
– “many-one” reduction (commonly) – “mapping” reduction (book)
February 2, 2024
CS21 Lecture 13
reduction from f no language A to
language B
Definition of reduction
AfB yes yes
• function f should be computable Definition: f : Σ*→ Σ* is computable if there
exists a TM Mf such that on every w ∈ Σ* Mf halts on w with f(w) written on its tape.
February 2, 2024 CS21 Lecture 13 5
Definition of reduction
• Notation: “A many-one reduces to B” is written
– “yes maps to yes and no maps to no” means:
w ∈ A maps to f(w) ∈ B & w ∉ A maps to f(w) ∉ B
• Bisatleastas“hard”asA
– more accurate: B at least as “expressive” as A
February 2, 2024 CS21 Lecture 13 6

Using reductions
Definition: A ≤m B if there is a computable function f such that for all w
w ∈ A ⇔ f(w) ∈ B
Theorem: if A ≤m B and B is decidable then
A is decidable
– decider for A: on input w, compute f(w), run
decider for B, do whatever it does.
February 2, 2024 CS21 Lecture 13 7
Using reductions
• Main use: given language NEW, prove it is undecidable by showing OLD ≤m NEW, where OLD known to be undecidable
– proof by contradiction
– if NEW decidable, then OLD decidable – OLD undecidable. Contradiction.
• common to reduce in wrong direction. • review this argument to check yourself.
February 2, 2024 CS21 Lecture 13 8
Using reductions
Theorem: if A ≤m B and B is RE then A is RE
– TM for recognizing A: on input w, compute f(w), run TM that recognizes B, do whatever it does.
• Main use: given language NEW, prove it is not RE by showing OLD ≤m NEW, where OLD known to be not RE.
February 2, 2024 CS21 Lecture 13 9
Many-one reduction example • Showed ETM undecidable. Consider:
February 2, 2024
co-ETM ={:L(M)≠Ø}
f • f() = yes where M’ is TM that
• on input x, if x ≠ w, f no then reject
• else simulate M on x, and accept if M does
• f clearly computable
CS21 Lecture 13 10
Many-one reduction example
AT M co-ET M
• yes maps to yes?
• f() = where M’ is TM that
• on input x, if x ≠ w, then reject
• else simulate M on x, and accept if M does
• f clearly computable
–if∈ATM thenf(M,w)∈co-ETM • no maps to no?
–if∉ATM thenf(M,w)∉co-ETM
February 2, 2024 CS21 Lecture 13 11
Undecidable problems
Theorem: The language
REGULAR = {: M is a TM and L(M) is
is undecidable.
– reduce from ATM (i.e. show ATM ≤m REGULAR) – what should f() produce?
February 2, 2024 CS21 Lecture 13 12

Undecidable problems
– f() = described below
on input x:
• if x has form 0n1n, accept
• else simulate M on w and accept x if M accepts
February 2, 2024
• is f computable?
• YES maps to YES?
∈ATM ⇒ f(M, w) ∈ REGULAR
• NO maps to NO?
∉ATM ⇒
f(M, w) ∉ REGULAR CS21 Lecture 13 13
Dec. and undec. problems
• the boundary between decidability and undecidability is often quite delicate
– seemingly related problems – one decidable
– other undecidable
• We will see two examples of this phenomenon next.
February 2, 2024 CS21 Lecture 13 14
Computation histories
• Recall configuration of a TM: string uqv with u,v ∈ Γ*, q ∈ Q
• The sequence of configurations M goes through on input w is a computation history of M on input w
– may be accepting, or rejecting
– reserve the term for halting computations
– nondeterministic machines may have several
computation histories for a given input.
February 2, 2024 CS21 Lecture 13 15
Linear Bounded Automata
LBA definition: TM that is prohibited from moving head off right side of input.
– machine prevents such a move, just like a TM prevents a move off left of tape
• How many possible configurations for a LBA M on input w with |w| = n, m states, and p = |Γ| ?
– counting gives: mnpn
February 2, 2024 CS21 Lecture 13 16
Dec. and undec. problems
• two problems we have seen with respect to TMs, now regarding LBAs:
– LBA acceptance:
ALBA ={:LBAMacceptsinputw}
– LBA emptiness:
ELBA ={:LBAMhasL(M)=Ø}
• Both decidable? both undecidable? one decidable?
February 2, 2024 CS21 Lecture 13 17
Dec. and undec. problems
Theorem: ALBA is decidable. Proof:
– input where M is a LBA
– key: only mnpn configurations
– if M hasn’t halted after this many steps, it must be looping forever.
– simulate M for mnpn steps
– if it halts, accept or reject accordingly,
– else reject since it must be looping
February 2, 2024 CS21 Lecture 13 18

Dec. and undec. problems Theorem: ELBA is undecidable.
– reduce from co-ATM (i.e. show co-ATM ≤m ELBA) – what should f() produce?
• produce LBA B that accepts exactly the accepting computation histories of M on input w
February 2, 2024 CS21 Lecture 13 19
Dec. and undec. problems
– f() = described below
on input x, check if x has form
#C1#C2#C3#…#Ck#
• check that C1 is the start configuration for M on input w
• check that Ci ⇒!Ci+1
• check that Ck is an accepting configuration for M
February 2, 2024
CS21 Lecture 13
• is B an LBA?
• is f computable?
• YES maps to YES?
∈ co-ATM ⇒ f(M, w) ∈ ELBA
• NO maps to NO?
∉ co-ATM ⇒ f(M, w) ∉ ELBA