Reduction Notes | EduRev

Created by: Vipul Dogra

: Reduction Notes | EduRev

 Page 1


Lecture 7
Page 2


Lecture 7
Reduction
“A is reducible to B” means I could solve A if I had a 
subroutine for B
Ex:
Finding the max element in a list is reducible to sorting
pf: sort the list in increasing order, take the last element
(A big hammer for a small problem, but never mind...)
Page 3


Lecture 7
Reduction
“A is reducible to B” means I could solve A if I had a 
subroutine for B
Ex:
Finding the max element in a list is reducible to sorting
pf: sort the list in increasing order, take the last element
(A big hammer for a small problem, but never mind...)
The Halting Problem
HALT
TM
 = { <M,w> | TM M halts on input w }
Theorem: The halting problem is undecidable
Proof:
A = A
TM
, B = HALT
TM  
Suppose I can reduce A to B.  We 
already know A is undecidable, so must be that B is, too.
Suppose TM R decides HALT
TM
.  Consider S: 
On input <M,w>, run R on it.  If it rejects, halt & reject; if it 
accepts, run M on w; accept/reject as it does.
Then S decides A
TM
, which is impossible.  R can’t exist.
Page 4


Lecture 7
Reduction
“A is reducible to B” means I could solve A if I had a 
subroutine for B
Ex:
Finding the max element in a list is reducible to sorting
pf: sort the list in increasing order, take the last element
(A big hammer for a small problem, but never mind...)
The Halting Problem
HALT
TM
 = { <M,w> | TM M halts on input w }
Theorem: The halting problem is undecidable
Proof:
A = A
TM
, B = HALT
TM  
Suppose I can reduce A to B.  We 
already know A is undecidable, so must be that B is, too.
Suppose TM R decides HALT
TM
.  Consider S: 
On input <M,w>, run R on it.  If it rejects, halt & reject; if it 
accepts, run M on w; accept/reject as it does.
Then S decides A
TM
, which is impossible.  R can’t exist.
Halt?
M,w
Simulate
acc
acc rej
rej
R:
S:
Yes
Page 5


Lecture 7
Reduction
“A is reducible to B” means I could solve A if I had a 
subroutine for B
Ex:
Finding the max element in a list is reducible to sorting
pf: sort the list in increasing order, take the last element
(A big hammer for a small problem, but never mind...)
The Halting Problem
HALT
TM
 = { <M,w> | TM M halts on input w }
Theorem: The halting problem is undecidable
Proof:
A = A
TM
, B = HALT
TM  
Suppose I can reduce A to B.  We 
already know A is undecidable, so must be that B is, too.
Suppose TM R decides HALT
TM
.  Consider S: 
On input <M,w>, run R on it.  If it rejects, halt & reject; if it 
accepts, run M on w; accept/reject as it does.
Then S decides A
TM
, which is impossible.  R can’t exist.
Halt?
M,w
Simulate
acc
acc rej
rej
R:
S:
Yes
Another Way
Rather than running R on <M,w>, and manipulating that 
answer, manipulate the input to build a new M’ so that 
R’s answer about <M’,w> directly answers the question 
of interest.
Speci?cally, build M’ as a clone of M, but modi?ed so 
that if M halts-and-rejects, M’ instead rejects by looping.
Then halt/not-halt for M’ == accept/reject for M
Again, this reduces A
TM
 to HALT
TM
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!