Undecidability Proofs and Reductions in Theory of Computation
CSE 105
Theory of
Computation
Alexander Tsiatas
Spring 2012
Theory of Computation Lecture Slides by Alexander Tsiatas is licensed under a Creative Commons
Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Based on a work at http://peerinstruction4cs.org.
Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org.
REDUCTIONS
More examples!!!!11
2
Thm. T = {<M> | M is a TM and both “101” and“111” are in L(M)} is undecidable
•
Proof by contradiction: (Reduce from A
TM
.)
•
Assume T is decidable by TM M
T
. Use M
T
to construct TM X that
decides A
TM
.
•
X(<M,w>):
–
Construct Z(m):
•
If m != “111” and m != “101” then reject.
•
Else: Run M(w), if it accepts then accept. If it rejects then reject (might loop in
which case obviously Z loops).
–
Run M
T
(<Z>). If it accepts then accept, otherwise reject.
•
But A
TM
is undecidable, a contradiction. So the assumption is false
and T is undecidable. QED.
3
What is L(Z)?
(a)
Σ
*
(b) {“101”, “111”}(c) empty set if M(w) rejects, and {“101”,”111”} if M(w) accepts.(d)
Σ
* if M(w) accepts, and {“101”,”111”} if M(w) does not accept•
We showed that
if
we have a solution to T
,
then
we have a solution to A
TM
.
•
What did we show exactly?
a)
A
TM
reduces to T.
b)
T reduces to A
TM
.
c)
T and A
TM
reduce to each other.
d)
None of the above or more than one of the
above.
4
We just did a reduction!
Thm. T = {<M> | M is a TM that accepts wR
whenever it accepts w} is undecidable
•
Proof by contradiction: (Reduce from A
TM
.)
•
Assume T is decidable by TM M
T
. Use M
T
to construct TM X that
decides A
TM
.
•
X(<M,w>):
–
Construct Z(m):
•
If m != “01” and m!= “10” then reject
•
If m == “01” accept
•
???
–
Run M
T
(<Z>). If it accepts then accept, otherwise reject.
•
But A
TM
is undecidable, a contradiction. So the assumption is false
and T is undecidable. QED.
5
How do we finish Z?
(a)
Run M(w), if it accepts then accept. If it rejects then reject (might loop in which case
obviously Z loops).
(b)
Run M(w), if it accepts then reject. If it rejects then accept (might loop in which case
obviously Z loops).
•
We showed that
if
we have a solution to T
,
then
we have a solution to A
TM
.
•
What did we show exactly?
a)
A
TM
reduces to T.
b)
T reduces to A
TM
.
c)
T and A
TM
reduce to each other.
d)
None of the above or more than one of the
above.
6
We just did a reduction!
MYSTERY_LANG ≤ A
CFG
•
Which of the following is true (given the
above statement is true):
a)
You can reduce from MYSTERY_LANG to A
CFG
.
b)
MYSTERY_LANG is decidable.
c)
A decider for A
CFG
(if it exists) could be used to
decide MYSTERY_LANG.
d)
All of the above
7
A
TM
≤ MYSTERY_LANG
•
Which of the following is true (given the
above statement is true):
a)
You can reduce from A
TM
to MYSTERY_LANG.
b)
MYSTERY_LANG is undecidable.
c)
A decider for MYSTERY_LANG (if it exists) could
be used to decide A
TM
.
d)
All of the above
8
MYSTERY_LANG ≤ A
TM
•
Which of the following is true (given the
statement above is true):
a)
MYSTERY_LANG is undecidable.
b)
A decider for A
TM
(if it exists) could be used to
decide MYSTERY_LANG.
c)
All of the above
9
MAPPING REDUCTIONS
Some more formalities….
10
Our reductions so far:
•
A ≤ B
–
Build a
decider
for A using a
decider
for B
–
No restrictions on what you can do with the
decider
for B
–
Does not generalize to
recognizability
•
To prove
recognizability
(or co-recognizability, or
lack thereof) by reductions, we need a
specific
type of reduction called a
mapping reduction
11
Mapping reductions
•
A ≤
m
B
•
First definition (there are 2 equivalent ones):
–
A special type of reduction
–
Build a TM for A using a TM for B…but:
•
Can only use B once
•
Cannot do anything after running B
•
Must use B’s output directly with no modification
12
This is a
mapping
reduction
•
E
TM
≤
m
EQ
TM
–
E
TM
= { <M>
| L(M) = {} }–
EQ
TM
= { <M
1
,M
2
>
| L(M
1
) = L(M
2
) }
•
Let M
EQ
decide EQ
TM
•
M
ETM
(
<
M
>
):
–
Let
M
x
be a TM that rejects all strings
–
Run M
EQ
(
<
M
,
M
x
>
)
•
If M
EQ
accepts, then accept. If it rejects, then reject.
13
Only uses M
EQ
once
Uses M
EQ
output with no modification
Doesn’t do anything after running M
EQ
Is this is a
mapping
reduction?
•
A
TM
≤
m
HALT
TM
?
–
A
TM
= { <M,w>
| M accepts w }
–
HALT
TM
= { <M,w>
| M halts on w) }
•
Let M
halt
decide HALT
TM
•
M
ATM
(
<
M,w
>
):
–
Run M
halt
(
<M,w>
). If it rejects, then reject.
–
Run
M
(
w
). If it accepts, then accept. If it rejects, then
reject.
a)
YES, it’s a mapping reduction
b)
NO, it’s not a mapping reduction
14
Mapping reductions:
a second definition
•
A ≤
m
B
•
Second definition:
–
There is a function f:
Σ
* ->
Σ
*
–
If f(x) = y, then:
•
y is in B if and only if x is in A.
–
f is computable by a TM that always halts
–
We say that f maps strings in A to strings in B
•
Note that A ≤
m
B also implies A ≤
m
B
15
What is the function f corresponding
to this mapping reduction?
•
E
TM
≤
m
EQ
TM
–
E
TM
= { <M>
| L(M) = {} }–
EQ
TM
= { <M
1
,M
2
>
| L(M
1
) = L(M
2
) }
•
Let M
EQ
decide EQ
TM
•
M
ETM
(
<
M
>
):
–
Let
M
x
be a TM that rejects all strings
–
Run M
EQ
(
<
M
,
M
x
>
)
•
If M
EQ
accepts, then accept. If it rejects, then reject.
a)
f(<M>) = <M>
b)
f(<M>) = <M,M
x
>
c)
f(<M,M
x
>) = <M>
d)
f(<M,M
x
>) = <M,M
x
>
16
Thm.: EQ
TM
is not recognizable
•
A
TM
= { <M,w> | M accepts w }•
EQ
TM
= { <M1
,M
2
> | L(M
1
) = L(M
2
) }
•
f(<M,w>) = <M
1
,M
2
> where:
–
M
1
= “On any input, reject”
–
M
2
= “On any input, run M on w. If it accepts, accept.”
•
Which mapping reduction does this f give?
a)
A
TM
≤
m
EQ
TM
b)
EQ
TM
≤
m
A
TM
c)
A
TM
≤
m
EQ
TM
d)
EQ
TM
≤
m
A
TM
17
We showed: A
TM
≤
m
EQ
TM
•
We know: A
TM
is NOT co-recognizable.
–
We showed this in a previous lecture
•
We showed: A
TM
is mapping reducible to
EQ
TM
.
–
We can “co-recognize” A
TM
by applying f and “co-
recognizing” EQ
TM
–
This means: if EQ
TM
is co-recognizable, then A
TM
is
co-recognizable.
–
We know A
TM
is not co-recognizable, though.
–
Contradiction! EQ
TM
is NOT co-recognizable.
–
The same as: EQ
TM
is NOT recognizable.
18
Thm.: EQ
TM
is not co-recognizable
•
A
TM
= { <M,w> | M accepts w }•
EQ
TM
= { <M1
,M
2
> | L(M
1
) = L(M
2
) }
•
f(<M,w>) = <M
1
,M
2
> where:
–
M
1
= “Accept”
–
M
2
= “On any input, run M on w. If it accepts, accept.”
•
Which mapping reduction does this f give?
a)
A
TM
≤
m
EQ
TM
b)
EQ
TM
≤
m
A
TM
c)
A
TM
≤
m
EQ
TM
d)
EQ
TM
≤
m
A
TM
19
We showed: A
TM
≤
m
EQ
TM
•
We know: A
TM
is NOT co-recognizable.
–
We showed this in a previous class
•
We showed: A
TM
is mapping reducible to
EQ
TM
.
–
We can “co-recognize” A
TM
by applying f and “co-
recognizing” EQ
TM
–
This means: if EQ
TM
is co-recognizable, then A
TM
is
co-recognizable.
–
We know A
TM
is not co-recognizable, though.
–
Contradiction! EQ
TM
is NOT co-recognizable.
20
So, we did TWO mapping reductions
•
A
TM
≤
m
EQ
TM
•
A
TM
≤
m
EQ
TM
•
We have shown: There is a language (
EQ
TM
) that is not
recognizable and also not co-recognizable!
•
In general: to show that a language L is NOT recognizable
–
Give a mapping reduction from A
TM
to L.
•
Pro tip
: Use A
TM
as the stock “language that’s recognizable
but not co-recognizable”
21
x 2
Explore undecidability proofs and reductions in the context of Theory of Computation through examples and explanations. Understand how problems are reduced to show undecidability, with demonstrations involving Turing Machines and languages. Gain insights into proving statements like the undecidability of certain sets and the implications of reductions between different problems.
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
CSE 105 Theory of Computation Alexander Tsiatas Spring 2012 Theory of Computation Lecture Slides by Alexander Tsiatas is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. Based on a work at http://peerinstruction4cs.org. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org.
More examples!!!!11 REDUCTIONS 2
Thm. T = {<M> | M is a TM and both 101 and 111 are in L(M)} is undecidable Proof by contradiction: (Reduce from ATM.) Assume T is decidable by TM MT. Use MT to construct TM X that decides ATM. X(<M,w>): Construct Z(m): If m != 111 and m != 101 then reject. Else: Run M(w), if it accepts then accept. If it rejects then reject (might loop in which case obviously Z loops). Run MT(<Z>). If it accepts then accept, otherwise reject. But ATM is undecidable, a contradiction. So the assumption is false and T is undecidable. QED. What is L(Z)? (a) * (c) empty set if M(w) rejects, and { 101 , 111 } if M(w) accepts. (d) * if M(w) accepts, and { 101 , 111 } if M(w) does not accept (b) { 101 , 111 } 3
We just did a reduction! We showed that if we have a solution to T, then we have a solution to ATM. What did we show exactly? a) ATM reduces to T. b) T reduces to ATM. c) T and ATM reduce to each other. d) None of the above or more than one of the above. 4
Thm. T = {<M> | M is a TM that accepts wR whenever it accepts w} is undecidable Proof by contradiction: (Reduce from ATM.) Assume T is decidable by TM MT. Use MT to construct TM X that decides ATM. X(<M,w>): Construct Z(m): If m != 01 and m!= 10 then reject If m == 01 accept ??? Run MT(<Z>). If it accepts then accept, otherwise reject. But ATM is undecidable, a contradiction. So the assumption is false and T is undecidable. QED. How do we finish Z? (a) Run M(w), if it accepts then accept. If it rejects then reject (might loop in which case obviously Z loops). (b) Run M(w), if it accepts then reject. If it rejects then accept (might loop in which case obviously Z loops). 5
We just did a reduction! We showed that if we have a solution to T, then we have a solution to ATM. What did we show exactly? a) ATM reduces to T. b) T reduces to ATM. c) T and ATM reduce to each other. d) None of the above or more than one of the above. 6
MYSTERY_LANG ACFG Which of the following is true (given the above statement is true): a) You can reduce from MYSTERY_LANG to ACFG. b) MYSTERY_LANG is decidable. c) A decider for ACFG (if it exists) could be used to decide MYSTERY_LANG. d) All of the above 7
ATM MYSTERY_LANG Which of the following is true (given the above statement is true): a) You can reduce from ATM to MYSTERY_LANG. b) MYSTERY_LANG is undecidable. c) A decider for MYSTERY_LANG (if it exists) could be used to decide ATM. d) All of the above 8
MYSTERY_LANG ATM Which of the following is true (given the statement above is true): a) MYSTERY_LANG is undecidable. b) A decider for ATM (if it exists) could be used to decide MYSTERY_LANG. c) All of the above 9
Some more formalities. MAPPING REDUCTIONS 10
Our reductions so far: A B Build a decider for A using a decider for B No restrictions on what you can do with the decider for B Does not generalize to recognizability To prove recognizability (or co-recognizability, or lack thereof) by reductions, we need a specific type of reduction called a mapping reduction 11
Mapping reductions A m B First definition (there are 2 equivalent ones): A special type of reduction Build a TM for A using a TM for B but: Can only use B once Cannot do anything after running B Must use B s output directly with no modification 12
This is a mapping reduction ETM m EQTM ETM = { <M> | L(M) = {} } EQTM = { <M1,M2> | L(M1) = L(M2) } Let MEQ decide EQTM METM(<M>): Let Mx be a TM that rejects all strings Run MEQ(<M,Mx>) If MEQ accepts, then accept. If it rejects, then reject. Uses MEQ output with no modification Only uses MEQ once Doesn t do anything after running MEQ 13
Is this is a mapping reduction? ATM m HALTTM? ATM = { <M,w> | M accepts w } HALTTM = { <M,w> | M halts on w) } Let Mhalt decide HALTTM MATM(<M,w>): Run Mhalt(<M,w>). If it rejects, then reject. Run M(w). If it accepts, then accept. If it rejects, then reject. a) YES, it s a mapping reduction b) NO, it s not a mapping reduction 14
Mapping reductions: a second definition A m B Second definition: There is a function f: * -> * If f(x) = y, then: y is in B if and only if x is in A. f is computable by a TM that always halts We say that f maps strings in A to strings in B Note that A mB also implies A m B 15
What is the function f corresponding to this mapping reduction? ETM m EQTM ETM = { <M> | L(M) = {} } EQTM = { <M1,M2> | L(M1) = L(M2) } Let MEQ decide EQTM METM(<M>): Let Mx be a TM that rejects all strings Run MEQ(<M,Mx>) If MEQ accepts, then accept. If it rejects, then reject. a) b) c) d) f(<M>) = <M> f(<M>) = <M,Mx> f(<M,Mx>) = <M> f(<M,Mx>) = <M,Mx> 16
Thm.: EQTM is not recognizable ATM = { <M,w> | M accepts w } EQTM = { <M1,M2> | L(M1) = L(M2) } f(<M,w>) = <M1,M2> where: M1= On any input, reject M2= On any input, run M on w. If it accepts, accept. Which mapping reduction does this f give? a) ATM m EQTM b) EQTM m ATM c) ATM m EQTM d) EQTM m ATM 17
We showed: ATMm EQTM We know: ATM is NOT co-recognizable. We showed this in a previous lecture We showed: ATM is mapping reducible to EQTM. We can co-recognize ATMby applying f and co- recognizing EQTM This means: if EQTM is co-recognizable, then ATM is co-recognizable. We know ATM is not co-recognizable, though. Contradiction! EQTM is NOT co-recognizable. The same as: EQTM is NOT recognizable. 18
Thm.: EQTM is not co-recognizable ATM = { <M,w> | M accepts w } EQTM = { <M1,M2> | L(M1) = L(M2) } f(<M,w>) = <M1,M2> where: M1= Accept M2= On any input, run M on w. If it accepts, accept. Which mapping reduction does this f give? a) ATM m EQTM b) EQTM m ATM c) ATM m EQTM d) EQTM m ATM 19
We showed: ATMm EQTM We know: ATM is NOT co-recognizable. We showed this in a previous class We showed: ATM is mapping reducible to EQTM. We can co-recognize ATMby applying f and co- recognizing EQTM This means: if EQTM is co-recognizable, then ATM is co-recognizable. We know ATM is not co-recognizable, though. Contradiction! EQTM is NOT co-recognizable. 20
So, we did TWO mapping reductions ATM m EQTM ATM m EQTM x 2 We have shown: There is a language (EQTM) that is not recognizable and also not co-recognizable! In general: to show that a language L is NOT recognizable Give a mapping reduction from ATM to L. Pro tip: Use ATMas the stock language that s recognizable but not co-recognizable 21
