Understanding the Limits of Computation in CMSC.281 Undecidability
Exploring the concept of undecidability in computing, we delve into the question of whether there are tasks that cannot be computed. The journey leads us to the theorem that the language ATM, defined as containing Turing Machine descriptions accepting input strings, is undecidable, showcasing the fundamental challenges in computation.
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 Undecidability
Are there things we cannot compute? Such questions are inherently hard. How do you prove something cannot be done?
Are there things we cannot compute? Such questions are inherently hard. Howd you prove something cannot be done? If you propose a method, and show it cannot work, you only proved that that particular method does not work.
Are there things we cannot compute? Such questions are inherently hard. How do you prove something cannot be done? If you propose a method, and show it cannot work, you only proved that that particular method does not work. A nasty way of saying this: I gave a proof of stupidity I seem to be too stupid to do this
Are there things we cannot compute? Such questions are inherently hard. How do you prove something cannot be done? If you propose a method, and show it cannot work, you only proved that that particular method does not work. We need to show that there cannot be ANY method!
Are there things we cannot compute? Such questions are inherently hard. How do you prove something cannot be done? If you propose a method, and show it cannot work, you only proved that that particular method does not work. We need to show that there cannot be ANY method! We will proceed to do that.
Are there things we cannot compute? Such questions are inherently hard. How do you prove something cannot be done? If you propose a method, and show it cannot work, you only proved that that particular method does not work. We need to show that there cannot be ANY method! We will proceed to do that. We can do that, because we have a precise notion of what can be computed.
Are there things we cannot compute? Theorem Let ATM be the language ATM={ <M,w> : M is a Tm, M accepts w. } ATMis not decidable
Are there things we cannot compute? Theorem Let ATM be the language ATM={ <M,w> : M is a Tm, M accepts w. } ATMis not decidable Technical remarks: we use <O> to denote an encoding of the object O. So <O> is simply a string of characters. We need this for the same reason we needed encodings to prove the existence of the Universal Turing Machine. We also need to encode pairs of objects as a single object but this is easy concatenate the strings
Are there things we cannot compute? Theorem Let ATM be the language ATM={ <M,w> : M is a Tm, M accepts w. } ATMis not decidable Proof: By contradiction. Assume there is a Tm that computes the function H(<M,w>)= accept if M, accepts x; reject if M rejects x Now, since H is computed by a Tm, we can use it as a subroutine. So th following function can also be computed by a Tm: D(<M>)= if [H(<M, <M>>) = accept] then reject; if [H(<M, <M>>) = reject] then accept
Are there things we cannot compute? Theorem Let ATM be the language ATM={ <M,w> : M is a Tm, M accepts w. } ATMis not decidable Proof: Assume there is a Tm that computes the function H(<M,w>)= accept if M, accepts x; reject if M rejects x D(<M>)= if [H(<M, <M>>) = accept] then reject; if [H(<M, <M>>) = reject] then accept Which means, in English D(<M>)= accept if M does not accept <M> = reject if M accepts <M>
Are there things we cannot compute? Theorem Let ATM be the language ATM={ <M,w> : M is a Tm, M accepts w. } ATMis not decidable Proof: Assume there is a Tm that computes the function H(<M,w>)= accept if M, accepts x; reject if M rejects x Then exist a Tm-computable D, such that D(<M>)= accept if M does not accept <M> = reject if M accepts <M>. What happens with D(<D>)???
Are there things we cannot compute? Theorem Let ATM be the language ATM={ <M,w> : M is a Tm, M accepts w. } ATMis not decidable Proof: Assume there is a Tm that computes the function H(<M,w>)= accept if M accepts w; reject if M rejects w Then exist a Tm-computable D, such that D(<M>)= accept if M does not accept <M> = reject if M accepts <M>. What happens with D(<D>)??? D(<D>)= accept if D does not accept <D> = reject if D accepts <D>.
Are there things we cannot compute? YES! .... and there a zillions of such functions! Recipe to prove f not computable: Assume it is computable. Show that the assumption allows you to decide ATM.
