SUNY Geneseo Department of Computer Science

Undecidability

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?

What if a method in a subclass generates an exception?

• Handle exception in that method (try - catch)
• Declare method as "throws Exception" and handle (try/catch) in caller
• Declare method as "throws Exception" and declare caller as "throws Exception"
• General rule: a method that generates an exception must either
  • Handle that exception itself, or
  • Be declared as throwing it, in which case it becomes a "generator" for its clients

Proving Problems Undecidable

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

• Consider...

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

• Contradiction: if a correct virus detector exists, then paradoxVirus forces it to be wrong (i.e., incorrect)
• So how can anti-virus software exist?
  • Catch "suspicious" actions
    • Future behavior vs present/past behavior
  • Effective vs correct
    • "Will infect" vs "might infect"
    • But you still want to be as accurate as possible about "might":

            boolean genericMightDetector(   P )
                return True

Given a program P, and an input, I, does P run on I ever...

• ... throw a null pointer exception
• ... attempt to divide by 0

    doOpposite( P )
        if P run on P divides by 0
            print "nyaah nyaah nyaah"
            stop
        else
            print 1 / 0

• doOpposite run on doOpposite cannot be correctly analyzed
• ... attempt to access an array outside its bounds

What if you just run P on I as a detector?

    halts( P, I )
        P(I)
        if P halted
            return true
        else
            return false

• Algorithm must always give an answer, but this one won't if P loops forever

Given a program, P, does P ever...

• ... throw a null pointer exception
• ... go into an infinite loop
  • A lot like the "enigma" program for the halting problem, except it doesn't have to deal with input

        enigma2
            if infiniteLoop(enigma2)
                then stop
            else
                loop forever

Next Lecture