SUNY Geneseo Department of Computer Science

Undecidability, Part 2

{Date}

CSci 141, Fall 2004
Prof. Doug Baldwin

Misc

Hand out Lab 14

Homework 3 due!

Final is Wed. Dec. 15, noon

SOFI's

Show that the following problem is undecidable:

Given the text of a program, P, and an input, I, does P run on I ever generate an exception?
- Or, a variation, given the text of a parameterless program, P, does P generate an exception?
General plan
- Assume algorithm throwsException(P,I) exists
- Ask a question about yourself
- Do the opposite
Mini-assignment: See how far you can get towards finishing the proof
What question to ask self?
- Something about future behavior
e.g., eye color: are my eyes brown?
- Contradiction: can my eyes not be brown?
Contradiction/paradox requires changing behavior to be different from what answer to question predicted
High-level paradoxical algorithm

    ExceptionParadox()
        if I will throw an exception
            then stop
        else
            x = 1 / 0 (throw an exception)

    ExceptionParadox()
        if ( throwsException(ExceptionParadox) )
            { }
        else {
            x = 1 / 0;
        }

Given the text of a program, P, will running P infect my computer with a virus?

    virusParadox
        if doesInfect( virusParadox )
            do nothing
        else
            infect this computer

Study group Tuesday, 1:00 PM, regular classroom

(No More Lectures)