SUNY Geneseo Department of Computer Science

The Halting Problem

Previous Lecture

Misc

SOFI's next Monday (May 2)

Final

• Monday, May 9, 8:00 AM
• Comprehensive but biased towards trees, limits
• Similar rules and format to hour exams
• 3 hours, designed for 2
• Donuts and cider

Questions?

Star in lab, and analyzing "for" loop?

• Rule for analyzing loops: add up the times that each iteration takes
• If every iteration does the same amount of work: multiply time for one iteration by the number of iterations
  • Equivalent to treating loop that repeats n times as n copies of its body

Sections 17.1 and 17.2

Introduction: halting problem

• i.e., infinite-loop checker

Quasi-Java for "terminate"

• ... which is an impossible algorithm

Impossible problem: Barber of Seville

Proving the halting problem is unsolvable

• Proof by contradiction
• Write new method, "enigma", that is infinite if input method is finite, otherwise finite - assuming that "terminate" can really work
• What does "enigma" do when run on itself?
  • If "terminate" says "enigma" is finite,
    • Then "enigma" runs forever
  • If "terminate" says "enigma" runs forever
    • Then "enigma" stops right away

Maybe the problem lies in "enigma", is it really codable? Or maybe "enigma" is illegal (violates precondition) input to "terminate"? Somehow it seems that if people can recognize when an algorithm does or doesn't halt, then an algorithm should be able to also.

• Compare to the Barber of Seville
• Barber of Seville shaves every (but only) man in Seville who doesn't shave himself
• Who is the barber?
  • Someone who doesn't shave self?
    • But then the barber shaves him, and since he is the barber, he shaves himself
  • Some who shaves self?
    • Then the barber can't shave him, so, again because he is the barber, he can't be someone who shaves himself
• The issue here isn't that people (or algorithms) need to be smarter to solve this, the issue is inherent in the problem. Same is the case for the Halting Problem.

Moral: limitations to CS - some things it just can't do

The Halting Problem Concretely

A Java Driver and Halting Detector (in stub form), with a "paradox" method that cannot be correctly analyzed for halting.

Proving Problems Undecidable

Given a program, P, with no input, does P infect a computer that runs it with a virus?

    paradoxVirus
        if paradoxVirus infects computer
            stop
        else
            infect computer w/ something

If a correct virus detector exists, then paradoxVirus forces it to be wrong -- contradiction between the detector being correct, and it producing a wrong answer on some input.

Mini-Assignment: You all know that "anti-virus" software exists -- how does it get around this undecidability result?

Next Lecture