Undecidability and Reductions in Theory of Computation
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.
