Halting Problem

Set cardinality in mathematics explores the concept of bijections, injections, and countability, showcasing how sets can have the same size even in infinite scenarios. The discussion delves into the notion of countable sets and the comparison between rational and integer numbers.

• Set theory
• Mathematics
• Bijection
• Countability
• Infinite sets

kendrycks Follow

Uploaded on Feb 23, 2025 | 0 Views

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.

Presentation Transcript

1. Halting Problem CSE 311 Fall 2023 Lecture 29

2. Announcements Remember to bring your Husky Card to the exam Kane 130 (starting at 4:30) on Monday. If you re sick (or have some other emergency) don t come; send Robbie an email. New video on panopto: a quick review of a few midterm problems. Remember only one late day can be used on HW8. We ll put the solutions on Ed on Ed at like 10:05 PM Saturday Review session Sunday Review session Sunday (time/location TBD) you ll get an email tomorrow morning!

3. Bijection Onto (aka surjection) One-to-one (aka injection) A function ? is one-to-one iff ? ?(? ? = ? ? ? = ?) A function ?:? ? is onto iff ? ? ? ?(? = ?(?)) Bijection A function ?:? ? is a bijection iff ? is one-to-one and onto A bijection maps every element of the domain to exactly the co-domain, and every element of the domain to exactly element of the domain. exactly one element of exactly one

4. Definition Two sets ?,? have the same size (same cardinality) if and only if there is a bijection ?:? ? This matches our intuition on finite sets. But it also works for infinite sets! Let s see just how infinite these sets are.

5. Countable Countable The set ? is countable iff there is an injection from ? to , Equivalently, ? is countable iff it is finite or there is a bijection from ? to , ,{?:? is an even integer} are all countable.

6. Lets Try one thats a little harder What about . There s gotta be more of those right? It s pretty intuitive to think there are more rationals than integers. The rationals are dense dense. Between every two rationals, there s another rational number. Or said in more intimidating fashion: between every two rationals there are infinitely many others!

7. The set of positive rational numbers 1/1 1/2 1/3 1/4 1/5 1/6 1/7 1/8 2/1 2/2 2/3 2/4 2/5 2/6 2/7 2/8 3/1 3/2 3/3 3/4 3/5 3/6 3/7 3/8 4/1 4/2 4/3 4/4 4/5 4/6 4/7 4/8 5/1 5/2 5/3 5/4 5/5 5/6 5/7 6/1 6/2 6/3 6/4 6/5 6/6 7/1 7/2 7/3 7/4 7/5 .... ... ... ... ... ... ... ... ... ... ... ...

8. In bijection with the natural numbers Order the rationals by their denominator (increasing), breaking ties by numerator. 1/1,1/2,1/3,2/3,1/4,3/4,1/5,2/5,3/5,4/5,1/6, ? ? =the ?th number in that list (indexed from 0) That s a bijection from to +(it s not a nice clean formula, but it s definitely a function)

9. In Bijection with the natural numbers How do we get all of ? We already know how to get twice as many map the even naturals to positives, and the odds to negatives. Like when we were mapping to . Fun fact: The order via diagonals technique is closely related to dovetailing a super-useful technique in compuatability theory (take 431 to learn more)

10. Uncountable Alright. There are clever ways to build bijections. Is there anything that s bigger than ? And like how would we prove it?

11. A proof idea A set is countable iff it can be listed (a list is a bijection with ). We ll take advantage of that to find an uncountable set. Claim is uncountable. Actually, it s easier if we show [0,1) is uncountable (i.e. real numbers between 0 and 1).

12. What do real numbers look like 0. 3 3 3 3 3 3 3 3 0. 2 7 2 7 2 8 5 4 0. 1 4 1 5 9 2 6 5 0. 2 2 2 2 2 2 2 2 0. 1 2 3 4 5 6 7 8 0. 9 8 7 6 5 4 3 2 0. 8 2 7 6 4 5 7 4 0. 5 9 4 2 7 5 1 7 A string of digits! Well not a string An infinitely long sequence of digits is more accurate.

13. Uncountable Suppose, for the sake of contradiction, that [0,1) is countable. Then there is a bijection ?: [0,1). Use that bijection to make the following table

14. Proof that [0,1) is not countable Suppose, for the sake of contradiction, that there is a list of them: Number Digits after decimal 0 1 2 3 4 5 6 7 0. 3 3 3 3 3 3 3 3 ?(0) 0. 2 7 2 7 2 8 5 4 ?(1) 0. 1 4 1 5 9 2 6 5 ?(2) 0. 2 2 2 2 2 2 2 2 ?(3) 0. 1 2 3 4 5 6 7 8 ?(4) 0. 9 8 7 6 5 4 3 2 ?(5) 0. 8 2 7 6 4 5 7 4 ?(6) 0. 5 9 4 2 7 5 1 7 ?(7)

15. Proof that [0,1) is not countable Suppose, for the sake of contradiction, that there is a list of them: Number Digits after decimal 0 1 2 3 4 5 6 7 0. 3 3 3 3 3 3 3 3 ?(0) Goal: find a real number between 0 and 1 that isn t on our table. (contradiction to bijection) 0. 2 7 2 7 2 8 5 4 ?(1) 0. 1 4 1 5 9 2 6 5 ?(2) 0. 2 2 2 2 2 2 2 2 ?(3) 0. 1 2 3 4 5 6 7 8 ?(4) 0. 9 8 7 6 5 4 3 2 ?(5) 0. 8 2 7 6 4 5 7 4 ?(6) 0. 5 9 4 2 7 5 1 7 ?(7)

16. Proof that [0,1) is not countable Suppose, for the sake of contradiction, that there is a list of them: Number Digits after decimal 0 1 2 3 4 5 6 7 How do we find a number that s not in our list? 0. 3 3 3 3 3 3 3 3 ?(0) 0. 2 7 2 7 2 8 5 4 ?(1) 0. 1 4 1 5 9 2 6 5 ?(2) Well let s make sure whatever our number is, it s not ?(0) 0. 2 2 2 2 2 2 2 2 ?(3) 0. 1 2 3 4 5 6 7 8 ?(4) 0. 9 8 7 6 5 4 3 2 ?(5) 0. 8 2 7 6 4 5 7 4 ?(6) 0. 5 9 4 2 7 5 1 7 ?(7)

17. Proof that [0,1) is not countable Suppose, for the sake of contradiction, that there is a list of them: Number Digits after decimal 0 1 2 3 4 5 6 7 0. 3 3 3 3 3 3 3 3 ?(0) Well let s make sure whatever our number is, it s not ?(0) 0. 2 7 2 7 2 8 5 4 ?(1) 0. 1 4 1 5 9 2 6 5 ?(2) Set the 0 column to not 3, say 7. 0. 2 2 2 2 2 2 2 2 ?(3) 0. 1 2 3 4 5 6 7 8 ?(4) 0. 9 8 7 6 5 4 3 2 ?(5) 0. 8 2 7 6 4 5 7 4 ?(6) 0. 5 9 4 2 7 5 1 7 ?(7) 0.7

18. Proof that [0,1) is not countable Suppose, for the sake of contradiction, that there is a list of them: Number Digits after decimal 0 1 2 3 4 5 6 7 0. 3 3 3 3 3 3 3 3 ?(0) Well let s make sure whatever our number is, it s not ?(1) 0. 2 7 2 7 2 8 5 4 ?(1) 0. 1 4 1 5 9 2 6 5 ?(2) Set the 1 column to not 7, say 3. 0. 2 2 2 2 2 2 2 2 ?(3) 0. 1 2 3 4 5 6 7 8 ?(4) 0. 9 8 7 6 5 4 3 2 ?(5) 0. 8 2 7 6 4 5 7 4 ?(6) 0. 5 9 4 2 7 5 1 7 ?(7) 0.73

19. Proof that [0,1) is not countable Suppose, for the sake of contradiction, that there is a list of them: Number Digits after decimal 0 1 2 3 4 5 6 7 0. 3 3 3 3 3 3 3 3 ?(0) Well let s make sure whatever our number is, it s not ?(2) 0. 2 7 2 7 2 8 5 4 ?(1) 0. 1 4 1 5 9 2 6 5 ?(2) Set the 2 column to not 1, say 7. 0. 2 2 2 2 2 2 2 2 ?(3) 0. 1 2 3 4 5 6 7 8 ?(4) 0. 9 8 7 6 5 4 3 2 ?(5) 0. 8 2 7 6 4 5 7 4 ?(6) 0. 5 9 4 2 7 5 1 7 ?(7) 0.737

20. Proof that [0,1) is not countable Suppose, for the sake of contradiction, that there is a list of them: Number Digits after decimal 0 1 2 3 4 5 6 7 0. 3 3 3 3 3 3 3 3 ?(0) Flipping Rule: Flipping Rule: let s set the ?? column to: column to: ? if if ?(?) s s ??? column is not column is not ? ? if if ? ? ???? column is 0. 2 7 2 7 2 8 5 4 ?(1) 0. 1 4 1 5 9 2 6 5 ?(2) column is ?. . 0. 2 2 2 2 2 2 2 2 ?(3) 0. 1 2 3 4 5 6 7 8 ?(4) 0. 9 8 7 6 5 4 3 2 ?(5) 0. 8 2 7 6 4 5 7 4 ?(6) 0. 5 9 4 2 7 5 1 7 ?(7) 0.73777733

21. Wrapping Up 0.73777733 What is it? It s a real number between 0 and 1(!!!) Is the number on the list? Well it s not ?(0), they differ in column 0. It s not ? 1 , they differ in column 1. It s not ?(?), they differ in column ?. But ?was a bijection. That s a contradiction!

22. Diagonalization This proof technique is called diagonalization Often Cantor s Diagonalization (after Cantor, who developed it). diagonalization

23. Takeaway 1 There are differing levels of infinity. Some infinite sets are equal in size. Other infinite sets are bigger than others. If this is mind-bending you re in good company. Cantor s contemporaries accused him of being a scientific charlatan and a corruptor of youth But Cantor was right and his ideas eventually were recognized as correct.

24. Lets Do Another! Let ? = 0,1 . Call a function ?: ?a binary valued function Intuitively, ? would be something like public boolean g(BigInteger input){ } If we could write that ? in Java. How many possible ?: ? are there?

25. Proof that [0,1) set of binary-valued functions is not countable Suppose, for the sake of contradiction, that there is a list of them: ? bijection from to function Output on ? Output on 1 Output on 2 Output on 3 Output on 4 Output on 5 Output on 6 Output on 7 1 0 1 1 1 0 1 1 ?(0) 0 1 1 0 0 1 0 0 ?(1) 1 1 1 0 0 0 1 1 ?(2) 0 0 0 0 0 0 0 0 ?(3) 1 0 1 1 1 0 1 1 ?(4) 0 0 0 1 0 1 1 1 ?(5) 1 1 0 1 0 1 1 0 ?(6) 0 2 0 1 1 0 1 0 ?(7)

26. Proof that [0,1) set of binary-valued functions is not countable Suppose, for the sake of contradiction, that there is a list of them: ? bijection from to function Output on ? Output on 1 Output on 2 Output on 3 Output on 4 Output on 5 Output on 6 Output on 7 1 0 1 1 1 0 1 1 ?(0) Goal: find a function ?????: 0,1 that isn t on our table. (contradiction to bijection) 0 1 1 0 0 1 0 0 ?(1) 1 1 1 0 0 0 1 1 ?(2) 0 0 0 0 0 0 0 0 ?(3) 1 0 1 1 1 0 1 1 ?(4) 0 0 0 1 0 1 1 1 ?(5) 1 1 0 1 0 1 1 0 ?(6) 0 2 0 1 1 0 1 0 ?(7)

27. Proof that [0,1) set of binary-valued functions is not countable Suppose, for the sake of contradiction, that there is a list of them: ? bijection from to function Output on ? Output on 1 Output on 2 Output on 3 Output on 4 Output on 5 Output on 6 Output on 7 How do we find a function not on our list? Well to make sure it s not ?(0) (the function in the first row) Have ?????0 = 0 1 0 1 1 1 0 1 1 ?(0) 0 1 1 0 0 1 0 0 ?(1) 1 1 1 0 0 0 1 1 ?(2) 0 0 0 0 0 0 0 0 ?(3) 1 0 1 1 1 0 1 1 ?(4) 0 0 0 1 0 1 1 1 ?(5) 1 1 0 1 0 1 1 0 ?(6) 0 ?? ? = 1 0 2 0 1 1 0 1 0 ?(7) ?????? =

28. Proof that [0,1) set of binary-valued functions is not countable Suppose, for the sake of contradiction, that there is a list of them: ? bijection from to function Output on ? Output on 1 Output on 2 Output on 3 Output on 4 Output on 5 Output on 6 Output on 7 How do we find a function not on our list? Well to make sure it s not ?(0) (the function in the first row) Have ?????0 = 0 1 0 1 1 1 0 1 1 ?(0) 0 1 1 0 0 1 0 0 ?(1) 1 1 1 0 0 0 1 1 ?(2) 0 0 0 0 0 0 0 0 ?(3) 1 0 1 1 1 0 1 1 ?(4) 0 0 0 1 0 1 1 1 ?(5) 1 1 0 1 0 1 1 0 ?(6) 0 ?? ? = 1 0 2 0 1 1 0 1 0 ?(7) ?????? =

29. Proof that [0,1) set of binary-valued functions is not countable Suppose, for the sake of contradiction, that there is a list of them: ? bijection from to function Output on ? Output on 1 Output on 2 Output on 3 Output on 4 Output on 5 Output on 6 Output on 7 How do we find a function not on our list? Well to make sure it s not ?(?) (the function in the ?? row) Have ?????? = 1 ? ? ? 1 0 1 1 1 0 1 1 ?(0) 0 1 1 0 0 1 0 0 ?(1) 1 1 1 0 0 0 1 1 ?(2) 0 0 0 0 0 0 0 0 ?(3) 1 0 1 1 1 0 1 1 ?(4) 0 0 0 1 0 1 1 1 ?(5) 1 1 0 1 0 1 1 0 ?(6) 0 ?? ? = 1 0 2 0 1 1 0 1 0 ?(7) ?????? =

30. Proof that [0,1) set of binary-valued functions is not countable Suppose, for the sake of contradiction, that there is a list of them: ? bijection from to function Output on ? Output on 1 Output on 2 Output on 3 Output on 4 Output on 5 Output on 6 Output on 7 How do we find a function not on our list? Well to make sure it s not ?(?) (the function in the ?? row) Have ?????? = 1 ? ? ? 1 0 1 1 1 0 1 1 ?(0) 0 1 1 0 0 1 0 0 ?(1) 1 1 1 0 0 0 1 1 ?(2) 0 0 0 0 0 0 0 0 ?(3) 1 0 1 1 1 0 1 1 ?(4) 0 0 0 1 0 1 1 1 ?(5) 1 1 0 1 0 1 1 0 ?(6) 1 ?? ? ? outputs 0 on input ? 0 ?? ? ? outputs 0 on input ? 0 2 0 1 1 0 1 0 ?(7) ?????? =

31. Wrapping up the proof Wrapping up the proof. Observe that ?????is a fully-defined function, and that it has as its domain and {0,1} as its codomain. It therefore should be in the co- domain of ?. But it cannot be on the list, as ?(?) is different from the function in the ?? row on input ? for all ?. This contradicts ? being onto! So we have that the set of binary-valued functions (with as their domains) is uncountable.

32. Our Second big takeaway How many Java methods can we write: public boolean g(int input) ? Can you list them? Yeah!! Put them in lexicographic i.e. in increasing order of length, with ties broken by alphabetical order. lexicographic order Wait that means the number of such Java programs is countable. And the number of functions we re supposed to write is uncountable.

33. Our Second big takeaway There are more functions ?: ? than there are Java programs to compute them. Some function must be uncomputable That is there is no piece of code which tells you the output of the function when you give it the appropriate input. uncomputable.

34. Not just Java This isn t just about java programs. (all we used about java was that its programs are strings) that s well every programming language. There are functions that simply cannot be computed. Doesn t matter how clever you are. How fancy your new programming language is. Just doesn t work.* *there s a difference between int and here, for the proof to work you really need all integers to be valid inputs, not just integers in a certain range.

35. Does this matter? It s even worse than that almost all functions are not computable. So how come this has never happened to you? This might not be meaningful yet. Almost all functions are also inexpressible in a finite amount of English (English is a language too!) You ve probably never decided to write a program that computes a function you couldn t describe in English Are there any problems anyone is interested computable? interested in solving that aren t

36. The Halting Problem

37. A Practical Uncomputable Problem Ever pressed the run button on your code and have it take a long time? Like an infinitely long time? What didn t your compiler like, tell you not It tells you when your code doesn t compile before it runs it why doesn t it check for infinite loops? not to push the button yet.

38. The Halting Problem The Halting Problem Given: source code for a program ? and ? an input we could give to ? Return: True if ? will halt on ?, False if it runs forever (e.g. goes in an infinite loop or infinitely recurses) This would be super useful to solve! We can t solve it let s find out why.

39. A Proof By Contradiction Suppose, for the sake of contradiction, there is a program ?, which given input P.java,? will accurately report ? would halt when run with input ? or ? will run forever on input ?. Important: Important: ? does not just compile P.java and run it. To count, ? needs to return halt or doesn t in a finite amount of time. And remember, it s not a good idea to say but ? has to run P.java to tell if it ll go into an infinite loop that s what we re trying to prove!!

40. A Very Tricky Program. Diagonal.java(String x){ Run H.exe on input <x, x> if(H.exe says x halts on x ) while(true){//Go into an infinite loop int x=2+2; } else //H.exe says x doesn t halt on x return; //halt. }

41. So, uhh thats a weird program. What do we do with it? USE IT TO BREAK STUFF Does Diagonal.java halt when its input is Diagonal.java? Let s assume it does and see what happens

42. A Very Tricky Program. Imagine Diagonal.java halts on Diagonal.java. Then H better say it halts. So it goes into an infinite loop. Diagonal.java(String x){ Run H.exe on input <x, x> if(H.exe says x halts on x ) while(true){//Go into an infinite loop int x=2+2; } else //H.exe says x doesn t halt on x return; //halt. } Wait shoot.

43. So, uhh thats a weird program. What do we do with it? USE IT TO BREAK STUFF Does Diagonal.java halt when its input is Diagonal.java? Let s assume it does and see what happens That didn t work. Let s assume it doesn t and see what happens

44. A Very Tricky Program. Imagine Diagonal.java doesn t halt on Diagonal.java. Then H better say it doesn t halt. So we go into the else branch. And it halts Diagonal.java(String x){ Run H.exe on input <x, x> if(H.exe says x halts on x ) while(true){//Go into an infinite loop int x=2+2; } else //H.exe says x doesn t halt on x return; //halt. } Wait shoot.

45. So, uhh thats a weird program. What do we do with it? USE IT TO BREAK STUFF Does Diagonal.java halt when its input is Diagonal.java? Let s assume it does and see what happens That didn t work. Let s assume it doesn t and see what happens That didn t work either. There s no third option. It either halts or it doesn t. And it doesn t do either. That s a contradiction! H.exe can t exist.

46. So So there is no general-purpose algorithm that decides whether any input program (on any input string). The Halting Problem is undecidable (i.e. uncomputable) there is no algorithm that solves every instance of the problem correctly.

47. What that does and doesnt mean That doesn t mean that there aren t algorithms that often get the answer right For example, if there s no loops, no recursion, and no method calls, it definitely halts. No problem with that kind of program existing. This isn t just a failure of computers if you think you hand, well you cant either. you can do this by

48. Takeaways Don t expect that there s a better IDE/better compiler/better programming language coming that will make it possible to tell if your code is going to hit an infinite loop. It s not coming.

49. More Uncomputable problems Imagine we gave the following task to 121 students: Write a program that prints Hello World Can you make an autograder? Technically NO!

50. More Uncomputable problems Imagine we gave the following task to 121 students: Write a program that prints Hello World Can you make an autograder? Technically NO! In practice, we declare the program wrong if it runs for 1 minute or so. That s not right 100% of the time, but it s good enough for your programming classes.

Load More ...