Reductions in Decidability and Tractability
CS21
Decidability
and
Tractability
Lecture 13
February 2, 2024
February 2, 2024
CS21 Lecture 13
2
Outline
•
reductions
•
many-one reductions
•
undecidable problems
–
computation histories
–
surprising contrasts between
decidable/undecidable
•
Rice’s Theorem
February 2, 2024
CS21 Lecture 13
3
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
4
Definition of reduction
•
More refined notion of reduction:
–
“many-one” reduction (commonly)
–
“mapping” reduction (book)
yes
no
yes
no
A
B
reduction
from
language A
to
language B
f
f
February 2, 2024
CS21 Lecture 13
5
Definition of reduction
yes
no
yes
no
A
B
f
f
February 2, 2024
CS21 Lecture 13
6
Definition of reduction
February 2, 2024
CS21 Lecture 13
7
Using reductions
February 2, 2024
CS21 Lecture 13
8
Using reductions
•
Main use:
given language NEW, prove it is
un
decidable by showing OLD
≤
m
NEW,
where OLD known to be
un
decidable
–
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
9
Using reductions
T
h
e
o
r
e
m
:
i
f
A
≤
m
B
a
n
d
B
i
s
R
E
t
h
e
n
A
i
s
R
E
P
r
o
o
f
:
–
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
10
Many-one reduction example
yes
no
yes
no
A
TM
co-E
TM
f
f
February 2, 2024
CS21 Lecture 13
11
Many-one reduction example
yes
no
yes
no
A
TM
co-E
TM
f
f
February 2, 2024
CS21 Lecture 13
12
Undecidable problems
T
h
e
o
r
e
m
:
T
h
e
l
a
n
g
u
a
g
e
REGULAR = {<M>: M is a TM and L(M) isregular}
is undecidable.
P
r
o
o
f
:
–
reduce from A
TM
(i.e. show A
TM
≤
m
REGULAR)
–
what should f(<M, w>) produce?
February 2, 2024
CS21 Lecture 13
13
Undecidable problems
P
r
o
o
f
:
–
f(<M, w>) = <M’> described below
on input x:
•
if x has form 0
n
1
n
, accept
•
else simulate M on w
and accept x if M accepts
February 2, 2024
CS21 Lecture 13
14
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
15
Computation histories
February 2, 2024
CS21 Lecture 13
16
Linear Bounded Automata
February 2, 2024
CS21 Lecture 13
17
Dec. and undec. problems
•
two problems we have seen with respect
to TMs, now regarding LBAs:
–
LBA acceptance:
A
LBA
= {<M, w> : LBA M accepts input w}
–
LBA emptiness:
E
LBA
= {<M> : LBA M has L(M) = Ø}
•
Both decidable? both undecidable? one
decidable?
February 2, 2024
CS21 Lecture 13
18
Dec. and undec. problems
T
h
e
o
r
e
m
:
A
L
B
A
i
s
d
e
c
i
d
a
b
l
e
.
Proof:
–
input <M, w> where M is a LBA
–
key: only
mnp
n
configurations
–
if M hasn’t halted after this many steps, it
must be looping forever.
–
simulate M for
mnp
n
steps
–
if it halts, accept or reject accordingly,
–
else reject since it must be looping
February 2, 2024
CS21 Lecture 13
19
Dec. and undec. problems
T
h
e
o
r
e
m
:
E
L
B
A
i
s
u
n
d
e
c
i
d
a
b
l
e
.
P
r
o
o
f
:
–
reduce from co-A
TM
(i.e. show co-A
TM
≤
m
E
LBA
)
–
what should f(<M, w>) produce?
–
Idea:
•
produce LBA B that accepts exactly the
accepting
computation histories
of M on input w
February 2, 2024
CS21 Lecture 13
20
Dec. and undec. problems
P
r
o
o
f
:
–
f(<M, w>) = <B> described below
Exploring the concepts of reductions, particularly many-one reductions, in the context of decidability and tractability. The lecture delves into the relationship between decidable and undecidable problems, highlighting examples like Rice's Theorem. It explains the definitions and implications of reductions and how they are utilized to prove undecidability, emphasizing the importance of proper reduction directions to maintain consistency in proofs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CS21 Decidability and Tractability Lecture 13 February 2, 2024
Outline reductions many-one reductions undecidable problems 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) A B f yes yes reduction from language A to language B f no no February 2, 2024 CS21 Lecture 13 4
Definition of reduction A B f yes yes f no no 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 A m B yes maps to yes and no maps to no means: w A maps to f(w) B & w A maps to f(w) B B is at least as hard as A 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 Proof: 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 Proof: 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: co-ETM = {<M> : L(M) } f(<M, w>) = <M > where M is TM that on input x, if x w, then reject else simulate M on x, and accept if M does f yes yes f no no co-ETM ATM f clearly computable February 2, 2024 CS21 Lecture 13 10
Many-one reduction example f(<M, w>) = <M > where M is TM that on input x, if x w, then reject else simulate M on x, and accept if M does f yes yes f no no co-ETM ATM f clearly computable yes maps to yes? if <M, w> ATM then f(M, w) co-ETM no maps to no? if <M, w> ATM then f(M, w) co-ETM February 2, 2024 CS21 Lecture 13 11
Undecidable problems Theorem: The language REGULAR = {<M>: M is a TM and L(M) is regular} is undecidable. Proof: reduce from ATM (i.e. show ATM m REGULAR) what should f(<M, w>) produce? February 2, 2024 CS21 Lecture 13 12
Undecidable problems Proof: f(<M, w>) = <M > described below is f computable? on input x: YES maps to YES? if x has form 0n1n, accept <M, w> ATM f(M, w) REGULAR else simulate M on w and accept x if M accepts NO maps to NO? <M, w> ATM f(M, w) REGULAR February 2, 2024 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 = {<M, w> : LBA M accepts input w} LBA emptiness: ELBA = {<M> : LBA M has L(M) = } Both decidable? both undecidable? one decidable? February 2, 2024 CS21 Lecture 13 17
Dec. and undec. problems Theorem: ALBA is decidable. Proof: input <M, w> 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. Proof: reduce from co-ATM (i.e. show co-ATM m ELBA) what should f(<M, w>) produce? Idea: 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 Proof: f(<M, w>) = <B> described below is B an LBA? on input x, check if x has form is f computable? #C1#C2#C3#...#Ck# check that C1 is the start configuration for M on input w YES maps to YES? <M, w> co-ATM f(M, w) ELBA NO maps to NO? check that Ci 1Ci+1 check that Ck is an accepting configuration for M <M, w> co-ATM f(M, w) ELBA February 2, 2024 CS21 Lecture 13 20
