SUNY Geneseo Department of Computer Science

Undecidability, Part 2

Previous Lecture

Misc

Interest Questionnaires

Practice Final is on the Web

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?

Undecidability

Is this problem undecidable: Given a method, M, does M's declaration start with the correct Java syntax (i.e., an access qualifier (public, etc.) followed by a result type followed by a name, etc.)?

• This is decidable
• Difference from undecidable problems?
  • Static structure of code vs dynamic behavior

How about this: Given two value-producing methods, M1 and M2, do they always return the same values (i.e., are they equivalent)?

• boolean areEquivalent( String m1, String m2 )
• Undecidable?
  • Can "areEquivalent" work on itself?
  • Algorithm that works by executing m1 & m2 can show non-equivalence, but never equivalence
  • Can you find two algorithms that create a paradox?
• Paradox
  • "If I am equivalent to something else
    • then act differently from it
    • else act the same as it"

        int reference()
            return 0

        int paradox()
            if areEquivalent(paradox, reference)
                return 1
            else
                return 0

• Creates a paradox: areEquivalent cannot correctly analyze "paradox"

(No More Lectures)