Sizes of Infinite Sets: Insights into Countably Infinite Concepts
Explore the fascinating world of countably infinite sets through informative images and explanations from a CSE 105 lecture on the Theory of Computability. Delve into the concepts of natural numbers, strings, Turing machines, languages, and the intriguing implications of the Pigeonhole Principle. Discover why the set of languages is not countably infinite while the set of Turing machines is, providing valuable insights into the complexities of infinite sets.
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
Announcements Homework HW8 due Tues 5/29 11am HW5 grades are out Monday is Memorial Day; no office hours, etc. Go see a parade, or some fireworks, or something TA Evaluations at the end of class! There s a lot of stuff in today s lecture
CSE 105 Theory of Computability Dr. Alexander Tsiatas Spring 2012 2
Sizes of infinite sets: countably infinite The natural numbers {0, 1, 2, 3, 4, } are countably infinite. Any set that s the same size as the natural numbers is countably infinite. 2 sets are the same sizeif there s a correspondence between them. Informal, but equivalent: a set is countably infinite if you can list them systematically like the natural numbers. The list will eventually contain ALL elements 4
Sizes of infinite sets: strings For any alphabet (here, {0, 1}), the set of all strings is countably infinite: , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, . 5
Sizes of infinite sets: Turing machines The set of all Turing machines is countably infinite: You can just encode TM s as strings. 6
Sizes of infinite sets: Languages Remember: a language is a set of strings. Can we make a list of ALL languages? Let s try 7
Sizes of infinite sets: Languages s1= s2=0 s3=1 s4=0 s5=01 s6=10 s7=11 s8=000 L1 L2 L3 L4 L5 L6 L7 L8 Claim: no matter the order you list languages, there is ALWAYS one that s not on the list. BAD = {si | si is NOT in Li} 8
So what?!?! No matter how you try to list languages, there s always a BAD language not on the list. The set of languages is NOT countably infinite! The set of TM s IS countably infinite! |Languages| >|TM s| Pigeonhole principle: there are languages that are NOT accepted by any TM. 9
ATM = {<M,w> | M is a TM, M accepts w} ATM is: a) A language b) An operation c) A set of strings d) A Turing Machine e) None or more than one of the above 10
THE TM ACCEPTANCE PROBLEM ATM 11
ATM = {<M,w> | M is a TM, M accepts w} ATM is Recognizable a) TRUE b) FALSE c) Other 12
At last the proof youve all been waiting for! ATM IS UNDECIDABLE 13
The Game Plan: Recall: ATM = {<M,w> | M is a TM, M accepts w} Thm: ATM is undecidable Proof by Contradiction: Assume (towards contradiction) that ATM is decidable, so there exists some TM MATM decides ATM. Want to show: A TM D that uses MATM as a subroutine, allowing D to do something impossible/contradictory. D(w): //w is a string What D is or what it does is totally up to us but we will have to be very clever to come up with something that will cause an impossibility/contradiction. Then, because we will have reached a contradiction, we will conclude that the assumption is false, and ATM is not decidable. 14
Lets look at MATM: Assume (towards contradiction) that ATM is decidable, so there exists some TM MATM decides ATM. Let TM G be a recognizer s.t. L(G) = {w | |w| is even} What will happen if we run MATM(<G,111>)? a) MATM accepts b) MATM rejects c) MATM loops d) Not enough information e) Other ATM = {<M,w> | M is a TM, M accepts w} 15
Proof: Thm: ATM = {<M,w> | M is a TM, M accepts w} is undecidable Assume (towards contradiction) that ATM is decidable, so there exists some TM MATM that decides ATM. Construct a TM D as follows: D(<M>): //input is a string description of a TM MATM(<M,<M>>) //MATM is a decider, so no infinite looping it will tell us if <M> is in L(M) or not, even if M loops on <M> If MATM accepts, we reject If MATM rejects, we accept // we do the opposite of MATM Now, it will take one more step to show how D can do something impossible 16
Pause to Examine TM D D(<M>): //input is a string description of a TM MATM(<M,<M>>) //MATM is a decider, so no infinite looping it will tell us if <M> is in L(M) or not, even if M loops on <M> If MATM accepts, we reject If MATM rejects, we accept // we do the opposite of MATM Let Mx be a TM, where L(Mx) = {}. What happens when we input Mx to D like this: D(<Mx>)? a) D accepts b) D rejects c) D loops d) Not enough information e) Other ATM = {<M,w> | M is a TM, M accepts w} 17
Pause to Examine TM D D(<M>): //input is a string description of a TM MATM(<M,<M>>) //MATM is a decider, so no infinite looping it will tell us if <M> is in L(M) or not, even if M loops on <M> If MATM accepts, we reject If MATM rejects, we accept // we do the opposite of MATM ML(w): Go into an infinite loop What happens when we input ML to D like this: D(<ML>)? a) D accepts b) D rejects c) D loops d) Not enough information e) Other ATM = {<M,w> | M is a TM, M accepts w} 18
Pause to Examine TM D D(<M>): //input is a string description of a TM MATM(<M,<M>>) //MATM is a decider, so no infinite looping it will tell us if <M> is in L(M) or not, even if M loops on <M> If MATM accepts, we reject If MATM rejects, we accept // we do the opposite of MATM Let Mv be a TM where L(Mv) = *. What happens when we input Mv to D like this: D(<Mv>)? a) D accepts b) D rejects c) D loops d) Not enough information e) Other ATM = {<M,w> | M is a TM, M accepts w} 19
Pause to Examine TM D D(<M>): //input is a string description of a TM MATM(<M,<M>>) //MATM is a decider, so no infinite looping it will tell us if <M> is in L(M) or not, even if M loops on <M> If MATM accepts, we reject If MATM rejects, we accept // we do the opposite of MATM What happens when we input D to D like this: D(<D>)? a) D accepts b) D rejects c) D loops d) Not enough information e) Other ATM = {<M,w> | M is a TM, M accepts w} 20
Proof: Thm: ATM = {<M,w> | M is a TM, M accepts w} is undecidable Assume (towards contradiction) that ATM is decidable, so some TM MATM decides ATM. Construct a TM D as follows: D(<M>): //input is a string description of a TM MATM(<M,<M>>) MATM is a decider, so it will either accept or reject (no infinite looping) If MATM accepts, we reject If MATM rejects, we accept // we do the opposite of MATM Run D(<D>). Observe that D(<D>) should accept when D(<D>) rejects, and D(<D>) should reject when D(<D>) accepts, a contradiction. Therefore the assumption is false, and ATM is undecidable. 21
Proving it is undecidable THE HALTING PROBLEM HALTTM 22
The Halting Problem HALTTM = {<M,w> | M is a TM and M halts on input w} Doesn t say if M accepts or rejects w, just that it halts Imagine we have a hypothetical TM Mhalt that decides HALTTM. Could we use Mhalt to build a decider for ATM? (recall: ATM = {<M,w> | M is a TM and M accepts w}) 23
Thm. HALTTM is undecidable. Proof by contradiction. Assume that HALTTM is decidable, and some TM Mhalt decides it. Construct a TM MATM that decides ATM: But is ATM is undecidable, a contradiction. So the assumption is false and HALTTM is undecidable. 24
We just did a reduction! We will do a LOT more of this next week! 25
TA Evaluations!!!!!111 Class number: CSE 105 TA s name: Srdjan Krstic OR Wenbo Zhao Evaluate whoever you had the MOST contact with Only evaluate ONEof the TA s If you didn t have much TA contact: leave it blank When finished: bring to front and you can go 26
