SUNY Geneseo Department of Computer Science
The
Halting Problem
{Date}
CSci 141, Fall 2003
Prof. Doug Baldwin
Return to
List of Lectures
Previous Lecture
End-of-Semester
CS Dept. holiday party
- Wed. Dec. 10, 3:00 PM
- South 309
- Sign up in Dept. office
Final
- Monday, Dec. 15, 8:00 AM
- Comprehensive but biased towards material since exam 2
- Same format and rules as hour exams
- Designed for 2 hours, 3 available
- Donuts & cider
- Sample questions will be on the Web
SOFIs
Interest Questionnaire
Questions?
The Halting Problem
Compiler translates the text of a program (e.g., Java source code) into executable
form and/or error messages
![[Translating Java into Machine Code or Errors]](compiler.gif)
Compilers detect some errors (e.g., undeclared variable names), but not others
(e.g., infinite loops)
Could you write an infinite loop detector?
- e.g., method "runsForever" that takes the text of another (parameterless)
method as its parameter, and returns true if that method never returns when
called, false if that method does return.
- Example Client and stub "runsForever"
in Java...
There exist problems that are well-defined but cannot be solved by algorithms!
(No More Lectures)