2008.08.13 | Marianne Dammand Iversen

Deciding the Undecidable - Who's That Rice Fellow Anyway?

Every computer program yields a number of questions. The big
one is "Does it work?", but more specifictasks of debugging and
optimization pose a wide variety of separate questions. In an ideal
world, automatic tools would provide the programmers with these answer,
but unfortunately the famous theorem by Rice tells us that this is only
possible for completely trivial questions. Rather than giving up,
programming language researchers have deconstructed the exact premises
of Rice's theorem to change theground rules sufficiently to allow
useful results. In fact, any weakening of these premises that is
logically possible has yielded an active area of research. This talk
will survey these areas and zoom in on some extreme points in the
design space of solutions.