Undecidability Consequences and Other Problems in Computer Science
Explore the undecidability of the Acceptance Turing Machine (ATM) and its implications in recognizing languages, including the relationship between decidability and recognizability. Discover the undecidability of the Halting Problem and its significance in computational theory.
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
CMSC 281 Consequences of the Undecidability of ATM
Other Undecidable Problems I stated that there are zillions of problems that are not decidable. Remember that ATM={<M,w> M accepts w} is not decidable. Note that ATM={<M,w> M accepts w} is trivially recognizable by a Tm: The Universal Turing Machine simulates M running on input w, and accepts iff M accepts w. Lemma: L and co-L are both recognizable iff L is decidable. (co-L is the set of strings not in L)
Other Undecidable Problems Lemma: L and co-L are both recognizable iff L is decidable Proof: A decider for L accepts L. Exchanging qacceptand qreject in this Tm gives us a Tm that accepts co-L. For the other direction, let M1and M2 be Tms that recognize L and co-L respectively. Consider the Tm M that on input x simulates both M1 and M2 (say it simulates one step of M1, then one step of M2, then the next step of M1, ) One of the two processes will terminate. M outputs the correct answer.
Other Undecidable Problems Lemma: L and co-L are both recognizable iff L is decidable We can now exhibit a language that cannot be recognized by any Tm. Claim: co-ATMis not c.e. Proof: if co-ATMwere c.e., since ATMis c.e., by the Lemma ATMwould be decidable.
Other Undecidable Problems L be a language recognized by a Tm M. We can assume wlog that for all strings x not in L M does not halt. Proof: modify M so that all transitions into the state qrejectgo instead to a new state qnew, and all transition from qnewlead back to qnew Such a machine rejects by not halting, and accepts by halting.
Other Undecidable Problems L be a language recognized by a Tm M. We can assume wlog that for all strings x not in L, M does not halt. Such a machine rejects by not halting, and accepts by halting. Consider the language HALTTM={<M,w> Tm M halts on input w} This is called the Halting Problem.
Other Undecidable Problems L be a language recognized by a Tm M. We can assume wlog that for all strings x not in L, M does not halt. Such a machine rejects by not halting, and accepts by halting. Consider the language HALTTM={<M,w> Tm M halts on input w} This is called the Halting Problem. Claim: The Halting Problem is undecidable. Proof: if it were decidable, we could decide ATM
Other Undecidable Problems L be a language recognized by a Tm M. We can assume wlog that for all strings x not in L, M does not halt. Such a machine rejects by not halting, and accepts by halting. Consider the language HALTTM={<M,w> Tm M halts on input w} This is called the Halting Problem. Claim: The Halting Problem is undecidable. Proof: if it were decidable, we could decide ATM Note: this is Theorem 5.1 in Sipser, who offers a slightly different proof.
Other Undecidable Problems Def. Tms M1and M2are equivalent if for every string x M1 halts on x iff M2halts on x and M1 accepts x iff M2accepts x (note that if we use Tms that reject by not halting, then the first condition suffices) EQTM={<M1,M2> M1and M2are equivalent} Theorem: EQTMis undecidable.
Other Undecidable Problems EQTM={<M1,M2> M1and M2are equivalent} Theorem: EQTMis undecidable. Proof: We will show that if it were decidable ATMwould be decidable. Given <M,w>, let M1be the Tm that on every input x simulates M with input w. So, for every input x, M1 halts (and accepts) iff M accepts w. Let M2 be the Tm that halts for no input. Then < M1,M2> is NOT in EQTMiff M accepts w, iff <M,w> is in ATM So, we produced an algorithm that decides ATM - a contradiction.
