SUNY Geneseo Department of Computer Science

The Halting Problem

Previous Lecture

Misc

Homework 3 due Thursday

End of Semester Stuff

• Final is Wed. Dec. 15, noon
  • Sample Exam on Web
  • Comprehensive, but more emphasis on material since 2nd hour exam
  • Designed for 2 hours, you have 3
    • 8 - 10 questions
  • Format and rules otherwise similar to hour exams
  • Donuts and Cider
• SOFI's in class Thursday (Dec. 9)

Questions?

Lists vs trees for homework

• Random trees are pretty well balanced
• i.e., Θ( logn ) height

Unsolvable Problems

Sections 17.1 and 17.2

1st section

• Compiler that can prove things about programs, calculate run times
• Does such a thing exist?
• Warning messages are syntax-related, don't catch termination of loops, how one could maybe check

What's with 2nd section?

• Why the goals of 1st section are impossible

A Game

In each round of play....

• I offer you a penny or a dime, and promise to give you one
• You guess which one I will give
• I give you a coin

Object: Correctly guess which coin I will give you

How well can you do in this game?

• (Not very)

Variation: I show you the algorithm I will use to select a coin to give you. Can you always win?

• (No)

My algorithm:

    get the guess
    if guess = pennny
        give dime
    else
        give penny

Barber of Seville example

• Paradoxical, answerless, question
• Definition: Barber is the man who shaves all men who don't shave themselves
• Paradox from "who shaves the barber?"
  • 1: The barber himself
    • Then barber doesn't shave only men who don't shave selves
  • 2: Someone else (another man)
    • Then barber doesn't shave self, so barber must shave him (the barber)
• Conclusion: definition of "barber" is impossible

Halting Demo

Problem to solve: Can an algorithm determine whether another algorithm halts?

• Given text of program, P, and an input, I, does P running on I ever halt?
• Halting problem

Program that demonstrates this problem, consisting of a Main Class and a HaltingDetector Class

Halting question can't be answered for some programs (and inputs)

Therefore halting problem cannot be solved by any algorithm (because there are some inputs for which the question is unanswerable)

The halting problem is "undecidable"

Some (many) instances solvable

There are inherent limits to computer science

But they are identifiable by computer science

Other Undecidable Problems

Given the text of a program, P, and an input, I, does P run on I ever generate an exception?

• Assume algorithm throwsException(P,I) exists
• General scheme for paradoxes
  • Ask a question about yourself
  • Do the opposite
• Variation: Given parameterless algorithm, P, does P throw an exception when run?
• Mini-Assignment: Try to fit the general scheme for paradoxes above to either the general (program and input) or variation (just program) forms of this specific problem.

Next Lecture