Undecidability and the Halting Problem
Delve into the fascinating world of undecidability, where problems remain unsolvable even with finite time algorithms. Learn about the Halting Problem and its implications, including the impossibility of determining if a program will halt or run infinitely. Discover the concept of NP-complete problems and the intriguing proof by contradiction. Uncover the complexities of uncomputable problems and the challenges they pose to computational systems.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Halting Problem CSE 417 AU21 Lecture 31
What (we think) the world looks like Assuming ? ?? 3-coloring (the decision version) Given a program, if I run it will it halt (or infinitely loop/recurse) Is this list sorted? ??-hard ?? ??- complete ? Finding an MST (not a decision problem) ? is definitely a subset of ?? (the verifier can just run the solving algorithm without any hint/certificate). We think that there are problems in NP that aren t in P (including all the NP-complete ones. 3-color a graph (return the coloring itself -- not a decision problem) Is there a spanning tree of weight ? 3-SAT
Undecidability We call a problem undecidable problem that produces the correct answer in finite time. undecidable if there is not an algorithm for that These are even harder than NP-problems. Even NP-complete problems have exponential time algorithms. Those are too slow to be super useful to people most of the time. But there is a way to solve them.
A Practical Uncomputable Problem Every pressed the run button on your code and have it take a long time? Like an infinitely long time? Why 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.
The Halting Problem The Halting Problem Input: source code for a program ? and ? an input we could give to ? Output: 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 (that is to say, the problem is undecidable). Let s find out why!
A Proof By Contradiction Suppose, for the sake of contradiction, there is a program H.exe, which given input P.java,? will accurately report ? would halt when run with input ? or ? will run forever on input ?. Important: Important: H.exe does not just compile P.java and run it. To count, H.exeneeds to return halt or doesn t in a finite amount of time. And remember, it s not a good idea to say but H has to run P.java to tell if it ll go into an infinite loop that s what we re trying to prove!!
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. }
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
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.
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
Imagine Diagonal.java doesnt halt on Diagonal.java. Then H better say it doesn t halt. So we go into the else branch. And it halts 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. } Wait darn it.
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.execan t exist.
So So there is no general-purpose algorithm that decides whether any input program (on any input string). The Halting Problem is undecidable every instance of the problem correctly. undecidable there is no algorithm that solves
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 writing a program to confirm just those programs will halt. This isn t just a failure of computers if you think you hand, well you cant either. you can do this by
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.
More Uncomputable problems Imagine we gave the following task to 142 students: Write a program that prints Hello World Can you make an autograder? Technically NO!
More Uncomputable problems Imagine we gave the following task to 142 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.
How Would we prove that? With a reduction. reduction. It s the same idea as reductions for NP-hardness. The only difference is we don t restrict to polynomial-time. Suppose, for the sake of contradiction, I can solve the HelloWorld problem. (i.e. on input P.java I can tell whether it eventually prints Hello World ) Let W.exe solve that problem. Consider this program
A Reduction Trick(P.java,x){ Run P.java on x //(but only simulate printing) Print Hello World } This actually prints Hello World if and only if P halts on x. If P does halt, then we get to the print line. If P does not halt, we never get a chance to print!
A Reduction Plug Trick into Wand .we solved the Halting Problem! If we want to solve the halting problem on P, x 1. Hard code P,x into Trick and run W on Trick. 2. Report whatever W does. And that s the right answer for the halting problem on P,x But we know we can t do that. So W existing is a contradiction, and we can t solve the Hello World problem either.
Solve the halting problem Simulate P print H W P.java Transform Input Hello World Solver W.exe Trick does not print Hello World P does not halt Transform Output
Fun (Scary?) Fact Rice s Theorem Says any non-trivial behavior of programs cannot be computed (in finite time).
Weve Covered A LOT Stable Matchings Proof fundamentals Modifications of BFS/DFS Divide & Conquer Dynamic Programming LPs Network Flow (and assignment problems) Reductions, P vs. NP Coping with NP-completeness Greedy algorithms
What Comes next? CSE 417 is intended as a last undergraduate course for those of you about to graduate (it s not a prereq for anything). We wanted to expose you to everything you are likely to need. But if you are hoping for more, consider: CSE 521 (Graduate algorithms) More math background expected, more approximation algorithms, and a few other topics. CSE 431 (Complexity theory) Proof-based (all your homework problems are proofs). More on NP, undecidability, other notions of hard. Courses in Math & AMATH (especially for LPs and network flow)
