Undecidability and Reductions in Theory of Computation
Reducibility
Chuck Cusack
Based on
–
M. Sipser, “Introduction to the Theory of Computation,” Second Edition,
Thomson/Course Technology, 2006, Chapter 5.
Review
•
Recall the
halting problem
:
HALT
TM
= {
M, w
|
M
is a
TM
that halts on input
w
}
•
We will prove that
HALT
TM
is not decidable.
•
Recall the language:
A
TM
= {
M, w
|
M
is a
TM
that accepts
w
}
•
Also recall that we proved the following theorem:
Thm 4.11
:
A
TM
= {
M, w
|
M
is an
TM
that accepts
w
} is
not decidable.
•
We will prove that
HALT
TM
is not decidable by using this
theorem.
HALT
TM
is not Decidable
Thm 5.1
:
HALT
TM
= {
M, w
|
M
is a
TM
that halts on input
w
}
is not decidable.
Proof
:
•
Assume
HALT
TM
is decidable.
•
Then some TM
R
decides
HALT
TM
.
•
Using
R
, we construct a TM
S
that will decide
A
TM
as follows:
S = “On input
M, w
, where
M
is a TM and
w
a string,
1.
Run TM
R
on input
M, w
.
// Determine if
M
halts with input
w.
2.
Reject if
R
rejects.
// If the machine doesn’t halt,
M, w
A
TM
. (Why?)
3.
If
R
accepts, simulate
M
on
w
until it halts.
// If it halts, then just run it.
4.
Accept if
M
accepts, reject if
M
rejects.”
// Return the answer
•
Clearly S decides
A
TM
.
•
But
A
TM
is not decidable, so we have a contradiction.
•
Therefore,
HALT
TM
is not decidable.
E
TM
is not Decidable
Thm 5.2
:
E
TM
=
{
M
|
M
is a
TM
and L(
M
) =
} is not
decidable.
Proof
:
•
Assume
E
TM
is decidable. Then some TM
R
decides
E
TM
.
•
Using
R
, we will construct a TM
S
that will decide
A
TM
.
•
Given input
M, w
,
we first construct a TM
M
1
as follows:
M
1
= “On input
x
:
1.
If
x
≠
w
, reject.
2.
If
x
=
w
, run
M
on input
w
and accept if
M
accepts.”
•
Notice that
–
if
M
accepts
w
,
M
1
accepts
w
and no other string.
–
if
M
does not accept
w
,
M
1
accepts no strings.
•
Therefore,
M
accepts
w
iff L(
M
1
)
≠
.
E
TM
is not Decidable
Proof continued
:
•
We constructed TM
M
1
s.t.
M
accepts
w
iff L(
M
1
)
≠
.
•
Thus, if we can determine whether or not L(
M
1
)
≠
, we can
decide whether or not
M
accepts
w
.
•
That is,
A
TM
reduces to
E
TM
.
•
Thus we construct a TM
S
that will decide
A
TM
as follows:
S = “On input
M, w
, where
M
is a TM and
w
a string,
1.
Construct TM
M
1
based on description of
M
and
w
.
2.
Run R on input
M
1
.
3.
Accept if R rejects, reject if R accepts.”
•
Clearly S decides
A
TM
.
•
But
A
TM
is not decidable, so we have a contradiction.
•
Therefore,
E
TM
is not decidable.
Reductions
•
Problem
A
reduces
to problem
B
if a solution to
B
can be
used to solve
A
.
•
If I can reduce problem
A
to problem
B
and I can solve
problem
B
, then I can solve problem
A
.
•
Example
–
Let
A
= “Given a list of names, find the alphabetically first one”
–
Let
B
= “Given a list of words, rearrange them so they are in
alphabetical order”
–
Notice that if the names on my list were in alphabetic order, the
first name on the list would be the one I want.
–
That is, I can reduce problem
A
to problem
B
.
–
Thus, a solution to problem
B
helps me solve problem
A
.
Bad Reduction Joke
When a certain mathematician wakes up every morning, he
sits at the table reading his favorite mathematics journal as
his wife makes coffee for him. One week she goes on
vacation, and when he wakes up, he realizes he has to make
his own coffee. Fortunately, he remembers how she did it—
she opens the cupboard, takes out the coffee and a mug, puts
a few scoops of coffee in the mug, adds water, and puts it in
the microwave. So he does it, and all is well.
Unfortunately, when he wakes up the next day, he again
realizes he has to make his own coffee. To his horror, he
discovers that the coffee and the mug are not in the
cupboard—they are on the counter. Thinking for a minute,
he realizes he can reduce the problem to one he has
previously solved. He puts the coffee and the mug into the
cupboard and shuts the door. He proceeds to make the
coffee as he did the previous day.
Reductions and Decidability
•
We have seen that if I can solve problem
B
and I can reduce
problem
A
to problem
B
, then I can solve problem
A
.
•
We can apply this to
decidability
–
Notice that
if A reduces to B and B is decidable, then A is
decidable
.
–
Thus, to prove a problem is decidable, you can show it can be
reduced to a decidable problem.
•
On the other hand, if I
cannot
solve problem
A
and I can
reduce problem
A
to problem
B
, then I
cannot
solve problem
B
.
•
This is because if I could solve problem
B
and I could
reduce problem
A
to problem
B
, this would lead to a
solution to problem
A
.
Reductions and Undecidability
•
We have seen that if I
cannot
solve problem
A
and I can
reduce problem
A
to problem
B
, then I
cannot
solve problem
B
.
•
We can apply this to
undecidability
–
Notice that
if A reduces to B and A is undecidable, then B is
undecidable
.
–
Thus, to prove a problem is undecidable, you can show some
undecidable problem can be reduced to it.
–
This is the technique we have used for the last two proofs.
•
It can be very easy to get this backwards, so be careful!
•
We will now prove a few more results using this technique.
Turing Machines and Regular Languages
•
Given a TM
M
, can we determine whether or not L(
M
) is
regular?
•
The language related to this problem is
REGULAR
TM
= {
M
|
M
is a
TM
and L(
M
) is a regular
language }
•
The question we want to answer is
Is
REGULAR
TM
decidable?
•
It should not surprise you to know that the answer is “no.”
•
We will prove this.
REGULAR
TM
is not Decidable
Thm 5.3
:
REGULAR
TM
= {
M
|
M
is a
TM
and L(
M
) is a
regular language }
is not decidable.
Proof idea (Very slightly modified from book’s proof)
:
•
We will show that we can reduce
A
TM
to
REGULAR
TM
.
•
That is, given an instance of
A
TM
, we will show how to solve
it using a TM that solves
REGULAR
TM
.
•
But
A
TM
is undecidable, so this is impossible.
•
Thus,
REGULAR
TM
is undecidable.
•
In order to do this, we will first create a TM
M
2
that will
accept a regular language iff
M
accepts
w
.
REGULAR
TM
is not Decidable
Proof idea continued
:
•
We want a TM
M
2
that will accept a regular language iff
M
accepts
w
.
•
TM
M
2
will operate as follows (
M
and
w
are built into it):
M
2
= “On input
x
:
1.
If
x
has the form 0
n
1
n
, accept.
2.
If
x
does not have that form, run
M
on input
w,
accepting if
M
accepts
w.”
•
Notice that
–
If
M
accepts
w
, L(
M
2
) =
∑*, a regular language, and
–
If
M
does not accept
w
, L(
M
2
) = {0
n
1
n
| n ≥ 0}, a non-regular
language.
•
That is, L(
M
2
) is a regular language iff
M
accepts
w.
REGULAR
TM
is not Decidable
Proof
:
•
Assume
REGULAR
TM
is decidable. Then some TM
R
decides
REGULAR
TM
.
•
Using
R
, we will construct a TM
S
that will decide
A
TM
.
S = “On input
M, w
, where
M
is a TM and
w
a string,
1.
Construct TM
M
2
as follows
M
2
= “On input
x
:
1.
If
x
has the form 0
n
1
n
, accept.
2.
If
x
does not have that form, run
M
on input
w,
accepting if
M
accepts
w.”
2.
Run R on input
M
2
.
//
R
accepts iff
M
accepts
w
.
3.
Accept if R accepts, reject if R rejects.”
•
Since
S
accepts iff
M
accepts
w
, we can decide
A
TM
.
•
This is a contradiction, since
A
TM
is undecidable.
•
Therefore, REGULAR
TM
is undecidable.
Rice’s Theorem
•
We have seen that we cannot tell whether or not the
language accepted by a TM is regular.
•
We can also prove that languages CFL
TM
, FINITE
TM
,
ODDLENGTH
TM
, (where each is defined similarly to
REGULAR
TM
) etc. are not decidable.
•
In fact, it can be shown that deciding
any
nontrivial property
(one that some but not all TMs have) of a TM language is
undecidable:
Thm 5.
π
:
For any given nontrivial property
P
of TMs,
P
TM
= {
M
|
M
is a
TM
and L(
M
) has property
P
}
is
not decidable.
•
See
Problem 5.28
and solution in
Sipser
for more details.
EQ
TM
is not Decidable
Thm 5.4
:
EQ
TM
= {
M, N
|
M
and
N
are
TMs
with L(
M
) =
L(
N
) }
is not decidable.
Proof
:
•
We will show that we can reduce
E
TM
to
EQ
TM
.
•
Assume EQ
TM
is decidable. Then some TM
R
decides
EQ
TM
.
•
Using
R
, we construct TM
S
that will decide
E
TM
as follows
S
= “On input
M
, where
M
is a TM:
1.
Run
R
on input
M, N
, where TM
N
rejects all inputs.
2.
Accept if
R
accepts, reject if
R
rejects.”
•
Since
S
accepts input
M
iff
L(M) = L(N) =
, we can
decide E
TM
.
•
This is a contradiction, since E
TM
is undecidable (Thm 5.2).
•
Therefore, EQ
TM
is undecidable.
Formalizing Reducibility
•
So far we have talked about reducing one problem to
another rather informally.
•
Now we formalize the notion by discussing
mapping
reducibility
(or
many-one reducibility
).
•
Before we can do that, we need to realize that a TM can
compute a function by replacing the input on the tape with
the desired output.
•
That is, instead of merely accepting or rejecting an input, we
can use a TM to perform computations.
•
Thus, if a TM implements function
f
, then given input
w
,
TM will output
f
(
w
).
Computable Functions
•
Definition
: A function
f
:
∑*→ ∑* is a
computable function
if some TM
M
, on every input
w
, halts with just
f
(
w
) on its
tape.
•
As we have discussed previously, any function that can be
computed by any reasonable model of computation can be
computed by a TM.
•
For instance, we know that we can implement addition,
multiplication, polynomial evaluation, etc. on a computer.
•
Therefore, we can construct a TM to compute these
functions.
•
Therefore, these functions are computable.
Mapping Reducible
•
Definition
: A language
A
is
mapping reducible
to language
B
if there is a computable function
f
:
∑*→ ∑*, where for
every string
w
,
w
A
f
(
w
)
B
•
If A is mapping reducible to B, we write
A
≤
m
B.
•
The function
f
is called the
reduction
of
A
to
B
.
•
In words, a function
f
is a reduction from
A
to
B
if every
string in
A
maps to a string in
B
, and every string not in
A
maps to a string not in
B
.
•
A reduction from
A
to
B
allows us to answer a question
about membership in
A
by converting it to a question about
membership in
B
.
•
If
A
reduces to
B
, to test if
w
A
, we can instead test if
f
(
w
)
B.
Reductions in Pictures
A
A
B
B
All Strings
All Strings
Mapping Reducibility and Decidability
Thm 5.22
:
If
A
≤
m
B
and
B
is decidable, then
A
is decidable.
Proof
:
•
Let TM
M
be a decider for
B
.
•
Since
A
≤
m
B
, there is some computable function
f
that maps
A
to
B
.
•
We construct a decider
N
for
A
as follows:
N
= “On input
w
:
1.
Compute
f
(
w
)
.
2.
Run
M
on input
f
(
w
)
and output whatever
M
outputs.”
•
Since
A
≤
m
B, w
A
f
(
w
)
B.
•
Thus,
N
accepts
w
M
accepts
f
(
w
)
w
A
.
•
Thus,
N
decides
A
.
Mapping Reducibility and Undecidability
•
We just saw
Thm 5.22
:
If
A
≤
m
B
and
B
is decidable, then
A
is decidable.
•
The following corollary should be easy to see:
Corollary 5.23
:
If
A
≤
m
B
and
A
is undecidable, then
B
is
undecidable.
–
Easy proof by contradiction
Summary/Review (so far)
•
If
A
≤
m
B
, and
f
is a reduction from
A
to
B
, then
–
w
A
f
(
w
)
B
–
y
B
does not
imply that
w
A s.t.
f
(
w
)=
y
–
An algorithm for
B
can be used for
A
–
An algorithm for
A
doesn’t help with
B
–
In some sense,
B
is at least as hard as
A
•
A
might be easier than
B
•
A
is not harder than
B
–
If I can’t find an algorithm for
B
, it doesn’t tell me anything about
A
–
If I can’t find an algorithm for
A
, it doesn’t tell me anything about
B
–
If I can prove there is no algorithm for
B
, it doesn’t tell me anything
about
A
However,
–
If I can prove there is no algorithm for
A
, there is no algorithm for
B
Quiz
•
If A is
undecidable
and
A
≤
m
B
, then
B
is_______?
–
undecidable
•
If A is
decidable
and
A
≤
m
B
, then
B
is_______?
–
We can’t say anything for sure
•
If B is
undecidable
and
A
≤
m
B
, then
A
is_______?
–
We can’t say anything for sure
•
If B is
decidable
and
A
≤
m
B
, then
A
is_______?
–
decidable
Mapping Reducibility and
The Halting Problem
•
We essentially used the previous corollary to prove several
of the results in these notes, although we didn’t actually
prove anything related to mapping reducibility.
•
In particular, we proved that
HALT
TM
is undecidable by
reducing from A
TM
.
•
But in all of these proofs we did not actually use the concept
of mapping reducibility in the proof.
•
Can we actually demonstrate that
A
TM
≤
m
HALT
TM
?
Halting Problem Revisited
•
We want to prove that
A
TM
≤
m
HALT
TM
.
•
To do so, we need to show there is a computable function
f
that maps an input
M, w
to output
M
'
, w
'
, where
M, w
A
TM
f
(
M, w
)=
M
'
, w
'
HALT
TM
•
That is, we need to construct a TM
F
which takes input
M,
w
and outputs
M
'
, w
'
, where
M
is a TM.
•
Notice that if
M
is not a TM, then
M, w
A
TM
, so we need
to make sure the output is not in
HALT
TM
.
•
This is easy enough—if the input is not valid, we output
“blah”, which certainly isn’t of the correct form.
Proof that
A
TM
≤
m
HALT
TM
•
To show that
A
TM
≤
m
HALT
TM
, we give the following TM that
computes the reduction.
F
= “On input
M, w
:
1.
If
M
is not a valid TM, output “blah”.
2.
Otherwise, construct the following TM
M
':
M
'
= “On input
x
:
1.
Run
M
on
x
.
2.
Accept if
M
accepts
3.
Loop if
M
rejects.
3.
Output
M
'
, w
”
•
Notice that
M
'
halts on
w
iff
M
accepts
w
.
•
Therefore, we can see that
M, w
A
TM
iff
M
'
, w
'
HALT
TM
.
Mapping Reducibility and Undecidability
•
It should be clear that a language
B
is decidable if and only
if
B
is decidable.
•
Thus, a language
B
is undecidable if and only if
B
is
undecidable.
•
Given this, we can strengthen Corollary 5.23:
Corollary 5.23b
:
If
A
is undecidable and
A
≤
m
B or
A
≤
m
B
,
then
B
is undecidable.
•
In fact, the proof of Theorem 5.2 sort of used a mapping of
the form
A
TM
≤
m
E
TM
.
–
Interesting fact:
A
TM
is not mapping reducible to
E
TM
–
See Problem 5.5 and solution for more details.
Reducibility and Turing-Recognizability
•
We can prove results about reductions and Turing-
recognizable languages that are analogous to the theorems
about reductions and decidability.
Thm 5.28
:
If
A
≤
m
B
and
B
is Turing-recognizable, then
A
is
Turing-recognizable.
Proof
:
•
Replace deciders in proof of Thm 5.22 with recognizers.
Corollary 5.29
:
If
A
≤
m
B
and
A
is not Turing-recognizable,
then
B
is not Turing-recognizable.
A
TM
and Turing-reducibility
•
Recall that
A
TM
is not Turing-recognizable.
•
Also observe that
A
≤
m
B
A
≤
m
B
•
This leads to the following useful result:
Corollary 5.29b
:
If
A
TM
≤
m
B,
then
B
is not Turing-recognizable.
Proof:
•
Since
A
TM
≤
m
B
A
TM
≤
m
B,
applying Corollary 5.29 and the
fact that
A
TM
is not Turing-recognizable, the result follows.
•
Thus, one way to show that a language is not Turing-
recognizable is to reduce
A
TM
to the
complement
of the
language.
•
Can we prove a language
B
is not Turing-recognizable by
proving
A
TM
≤
m
B
? Why or why not?
A final Theorem about
EQ
TM
Thm 5.4
:
EQ
TM
= {
M, N
|
M
and
N
are
TMs
with L(
M
) =
L(
N
) }
is neither Turing-recognizable nor co-Turing-
recognizable.
Proof:
•
Time permitting, work it out.
•
Otherwise, read the proof in
Sipser
Section 5.3.
Explore the undecidability of the halting problem and ATM, using reductions to show their non-decidability. Discover how problems are reduced from A to B in computation theory, enabling the solution of one problem by solving another.
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
Reducibility Chuck Cusack Based on M. Sipser, Introduction to the Theory of Computation, Second Edition, Thomson/Course Technology, 2006, Chapter 5.
Review Recall the halting problem: HALTTM = { M, w | M is a TM that halts on input w } We will prove that HALTTM is not decidable. Recall the language: ATM= { M, w | M is a TM that accepts w } Also recall that we proved the following theorem: Thm 4.11: ATM= { M, w | M is an TM that accepts w } is not decidable. We will prove that HALTTM is not decidable by using this theorem.
HALTTM is not Decidable Thm 5.1: HALTTM = { M, w | M is a TM that halts on input w } is not decidable. Proof: Assume HALTTM is decidable. Then some TM R decides HALTTM. Using R, we construct a TM S that will decide ATM as follows: S = On input M, w , where M is a TM and w a string, 1. Run TM R on input M, w . // Determine if M halts with input w. 2. Reject if R rejects. // If the machine doesn t halt, M, w ATM. (Why?) 3. If R accepts, simulate M on w until it halts. // If it halts, then just run it. 4. Accept if M accepts, reject if Mrejects. // Return the answer Clearly S decides ATM. But ATM is not decidable, so we have a contradiction. Therefore, HALTTM is not decidable.
ETM is not Decidable Thm 5.2: ETM= { M | M is a TM and L(M) = } is not decidable. Proof: Assume ETM is decidable. Then some TM R decides ETM. Using R, we will construct a TM S that will decide ATM. Given input M, w , we first construct a TM M1 as follows: M1= On input x: 1. If x w, reject. 2. If x = w, run M on input w and accept if Maccepts. Notice that if M accepts w, M1 accepts w and no other string. if M does not accept w, M1 accepts no strings. Therefore, M accepts w iff L(M1) .
ETM is not Decidable Proof continued: We constructed TM M1 s.t. M accepts w iff L(M1) . Thus, if we can determine whether or not L(M1) , we can decide whether or not M accepts w. That is, ATM reduces to ETM. Thus we construct a TM S that will decide ATM as follows: S = On input M, w , where M is a TM and w a string, 1. Construct TM M1 based on description of M and w. 2. Run R on input M1 . 3. Accept if R rejects, reject if R accepts. Clearly S decides ATM. But ATM is not decidable, so we have a contradiction. Therefore, ETM is not decidable.
Reductions Problem Areduces to problem B if a solution to B can be used to solve A. If I can reduce problem A to problem B and I can solve problem B, then I can solve problem A. Example Let A= Given a list of names, find the alphabetically first one Let B= Given a list of words, rearrange them so they are in alphabetical order Notice that if the names on my list were in alphabetic order, the first name on the list would be the one I want. That is, I can reduce problem A to problem B. Thus, a solution to problem B helps me solve problem A.
Bad Reduction Joke When a certain mathematician wakes up every morning, he sits at the table reading his favorite mathematics journal as his wife makes coffee for him. One week she goes on vacation, and when he wakes up, he realizes he has to make his own coffee. Fortunately, he remembers how she did it she opens the cupboard, takes out the coffee and a mug, puts a few scoops of coffee in the mug, adds water, and puts it in the microwave. So he does it, and all is well. Unfortunately, when he wakes up the next day, he again realizes he has to make his own coffee. To his horror, he discovers that the coffee and the mug are not in the cupboard they are on the counter. Thinking for a minute, he realizes he can reduce the problem to one he has previously solved. He puts the coffee and the mug into the cupboard and shuts the door. He proceeds to make the coffee as he did the previous day.
Reductions and Decidability We have seen that if I can solve problem B and I can reduce problem A to problem B, then I can solve problem A. We can apply this to decidability Notice that if A reduces to B and B is decidable, then A is decidable. Thus, to prove a problem is decidable, you can show it can be reduced to a decidable problem. On the other hand, if I cannot solve problem A and I can reduce problem A to problem B, then I cannot solve problem B. This is because if I could solve problem B and I could reduce problem A to problem B, this would lead to a solution to problem A.
Reductions and Undecidability We have seen that if I cannot solve problem A and I can reduce problem A to problem B, then I cannot solve problem B. We can apply this to undecidability Notice that if A reduces to B and A is undecidable, then B is undecidable. Thus, to prove a problem is undecidable, you can show some undecidable problem can be reduced to it. This is the technique we have used for the last two proofs. It can be very easy to get this backwards, so be careful! We will now prove a few more results using this technique.
Turing Machines and Regular Languages Given a TM M, can we determine whether or not L(M) is regular? The language related to this problem is REGULARTM = { M | M is a TM and L(M) is a regular language } The question we want to answer is Is REGULARTM decidable? We will prove this. It should not surprise you to know that the answer is no.
REGULARTM is not Decidable Thm 5.3:REGULARTM = { M | M is a TM and L(M) is a regular language }is not decidable. Proof idea (Very slightly modified from book s proof): We will show that we can reduce ATM to REGULARTM. That is, given an instance of ATM, we will show how to solve it using a TM that solves REGULARTM. But ATM is undecidable, so this is impossible. Thus, REGULARTMis undecidable. In order to do this, we will first create a TM M2that will accept a regular language iff M accepts w.
REGULARTM is not Decidable Proof idea continued: We want a TM M2that will accept a regular language iff M accepts w. TM M2 will operate as follows (M and w are built into it): M2= On input x: 1. If x has the form 0n1n, accept. 2. If x does not have that form, run M on input w, accepting if M accepts w. Notice that If M accepts w, L(M2) = *, a regular language, and If M does not accept w, L(M2) = {0n1n| n 0}, a non-regular language. That is, L(M2) is a regular language iff M accepts w.
REGULARTM is not Decidable Proof: Assume REGULARTM is decidable. Then some TM R decides REGULARTM. Using R, we will construct a TM S that will decide ATM. S = On input M, w , where M is a TM and w a string, 1. Construct TM M2 as follows M2= On input x: 1. If x has the form 0n1n, accept. 2. If x does not have that form, run M on input w, accepting if M accepts w. 2. Run R on input M2 . // R accepts iff M accepts w. 3. Accept if R accepts, reject if R rejects. Since S accepts iff M accepts w, we can decide ATM. This is a contradiction, since ATM is undecidable. Therefore, REGULARTM is undecidable.
Rices Theorem We have seen that we cannot tell whether or not the language accepted by a TM is regular. We can also prove that languages CFLTM , FINITETM , ODDLENGTHTM , (where each is defined similarly to REGULARTM) etc. are not decidable. In fact, it can be shown that deciding any nontrivial property (one that some but not all TMs have) of a TM language is undecidable: Thm 5. :For any given nontrivial property P of TMs, PTM = { M | M is a TM and L(M) has property P }is not decidable. See Problem 5.28 and solution in Sipser for more details.
EQTM is not Decidable Thm 5.4:EQTM= { M, N | M and N are TMs with L(M) = L(N) }is not decidable. Proof: We will show that we can reduce ETM to EQTM. Assume EQTM is decidable. Then some TM R decides EQTM. Using R, we construct TM S that will decide ETM as follows S= On input M , where M is a TM: 1. Run R on input M, N , where TM N rejects all inputs. 2. Accept if R accepts, reject if Rrejects. Since S accepts input M iff L(M) = L(N) = , we can decide ETM. This is a contradiction, since ETM is undecidable (Thm 5.2). Therefore, EQTM is undecidable.
Formalizing Reducibility So far we have talked about reducing one problem to another rather informally. Now we formalize the notion by discussing mapping reducibility (or many-one reducibility). Before we can do that, we need to realize that a TM can compute a function by replacing the input on the tape with the desired output. That is, instead of merely accepting or rejecting an input, we can use a TM to perform computations. Thus, if a TM implements function f, then given input w, TM will output f(w).
Computable Functions Definition: A function f: * * is a computable function if some TM M, on every input w, halts with just f(w) on its tape. As we have discussed previously, any function that can be computed by any reasonable model of computation can be computed by a TM. For instance, we know that we can implement addition, multiplication, polynomial evaluation, etc. on a computer. Therefore, we can construct a TM to compute these functions. Therefore, these functions are computable.
Mapping Reducible Definition: A language A is mapping reducible to language B if there is a computable function f: * *, where for every string w, w A f(w) B If A is mapping reducible to B, we write A mB. The function f is called the reduction of A to B. In words, a function f is a reduction from A to B if every string in A maps to a string in B, and every string not in A maps to a string not in B. A reduction from A to B allows us to answer a question about membership in A by converting it to a question about membership in B. If A reduces to B, to test if w A, we can instead test if f(w) B.
Reductions in Pictures All Strings All Strings A B A B
Mapping Reducibility and Decidability Thm 5.22:If A mB and B is decidable, then A is decidable. Proof: Let TM M be a decider for B. Since A mB, there is some computable function f that maps A to B. We construct a decider N for A as follows: N= On input w: 1. Compute f(w). 2. Run M on input f(w) and output whatever Moutputs. Since A mB, w A f(w) B. Thus, N accepts w M accepts f(w) w A. Thus, N decides A.
Mapping Reducibility and Undecidability We just saw Thm 5.22:If A mB and B is decidable, then A is decidable. The following corollary should be easy to see: Corollary 5.23:If A mB and A is undecidable, then B is undecidable. Easy proof by contradiction
Summary/Review (so far) If A mB, and f is a reduction from A to B, then w A f(w) B y Bdoes not imply that w A s.t. f(w)=y An algorithm for B can be used for A An algorithm for Adoesn t help with B In some sense, B is at least as hard as A A might be easier than B A is not harder than B If I can t find an algorithm for B, it doesn t tell me anything about A If I can t find an algorithm for A, it doesn t tell me anything about B If I can prove there is no algorithm for B, it doesn t tell me anything about A However, If I can prove there is no algorithm for A, there is no algorithm for B
Quiz If A is undecidable and A mB , then B is_______? undecidable If A is decidable and A mB , then B is_______? We can t say anything for sure If B is undecidable and A mB , then A is_______? We can t say anything for sure If B is decidable and A mB , then A is_______? decidable
Mapping Reducibility and The Halting Problem We essentially used the previous corollary to prove several of the results in these notes, although we didn t actually prove anything related to mapping reducibility. In particular, we proved that HALTTM is undecidable by reducing from ATM. But in all of these proofs we did not actually use the concept of mapping reducibility in the proof. Can we actually demonstrate that ATM mHALTTM?
Halting Problem Revisited We want to prove that ATM mHALTTM. To do so, we need to show there is a computable function f that maps an input M, w to output M', w' , where M, w ATM f( M, w )= M', w' HALTTM That is, we need to construct a TM F which takes input M, w and outputs M', w' , where M is a TM. Notice that if M is not a TM, then M, w ATM , so we need to make sure the output is not in HALTTM. This is easy enough if the input is not valid, we output blah , which certainly isn t of the correct form.
Proof that ATMmHALTTM To show that ATM mHALTTM, we give the following TM that computes the reduction. F= On input M, w : 1. If Mis not a valid TM, output blah . 2. Otherwise, construct the following TM M': M' = On input x: 1. Run M on x. 2. Accept if M accepts 3. Loop if M rejects. 3. Output M', w Notice that M' halts on w iff M accepts w. Therefore, we can see that M, w ATM iff M', w' HALTTM.
Mapping Reducibility and Undecidability It should be clear that a language B is decidable if and only if B is decidable. Thus, a language B is undecidable if and only if B is undecidable. Given this, we can strengthen Corollary 5.23: Corollary 5.23b:If A is undecidable and A mB orA mB, then B is undecidable. In fact, the proof of Theorem 5.2 sort of used a mapping of the form ATM mETM. Interesting fact: ATM is not mapping reducible to ETM See Problem 5.5 and solution for more details.
Reducibility and Turing-Recognizability We can prove results about reductions and Turing- recognizable languages that are analogous to the theorems about reductions and decidability. Thm 5.28:If A mB and B is Turing-recognizable, then A is Turing-recognizable. Proof: Replace deciders in proof of Thm 5.22 with recognizers. Corollary 5.29:If A mB and A is not Turing-recognizable, then B is not Turing-recognizable.
ATM and Turing-reducibility Recall that ATM is not Turing-recognizable. Also observe that A mB A mB This leads to the following useful result: Corollary 5.29b:If ATM mB, then B is not Turing-recognizable. Proof: Since ATM mB ATM mB, applying Corollary 5.29 and the fact that ATM is not Turing-recognizable, the result follows. Thus, one way to show that a language is not Turing- recognizable is to reduce ATM to the complement of the language. Can we prove a language B is not Turing-recognizable by proving ATM mB? Why or why not?
A final Theorem about EQTM Thm 5.4:EQTM= { M, N | M and N are TMs with L(M) = L(N) }is neither Turing-recognizable nor co-Turing- recognizable. Proof: Time permitting, work it out. Otherwise, read the proof in Sipser Section 5.3.
