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 TMRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!