Rice's Theorem

and what it means for you! :)

Created by Simon Cross / @hodgestar

What the heck is Rice's Theorem?

Some things are just unpossible!

Which things? Glad you asked! :)

Properties of computable partial functions

Formal(ish) statement

Given a non-trivial property of computable partial functions the problem of whether a particular program computes such a function is undecidable

Non-trivial

  • A least one function that has the property
  • A least one function that doesn't have the property
See Wikipedia for the gory details. :)

Kinds of properties

Works for:

Properties that refer to behaviour

Properties that refer to input and output only

Doesn't work for:

Properties that refer to the implementation

  • Number of lines of code
  • Number of for-loops
  • Whether the code is syntactically correct

Sketch of a proof ...

... in Python!


def has_cool_property(f):
    """Returns True if f has this cool property,
       False otherwise."""
    # XXX: Put magic here!

def tiny_cool_function(*args, **kw):
    """Tiny function we wrote to show the cool property
       is sometimes met."""
    # XXX: Write this.

def halts(a, i):
    """Returns True if a halts given input i."""
    def t(*args, **kw):
        a(i)  # this is just here to mess with has_cool_property
        return tiny_cool_function(*args, **kw)
    return has_cool_property(t)
					

So these implications you promised?

QA and testing

Security and sandboxes

Compiling and static analysis

Non-implications

a.k.a. things that might work

Upfront design

If you want a property, design it in up front ...

because you won't be able to check later. :/

HALT?

BY Simon Cross / hodgestar.za.net

What made you look into all this?!

Blame PERL!

It's unparsable. :/

Its grammar is ambiguous in crazy ways:

whatever / 25 ; # / ; die "this dies!";

If you ever need to feel great about using Python:

An unrelated cool thing:

“Compiling a program and staring at a screenfull of nagging messages is a dull and exasperating activity.”
“In fact, I would venture to say that after a couple days playing with Python, many faculty who are now teaching C++ would know Python better.”

Ideas generated by questions and comments after the talk

  • Scalability is another property one can't tack on to programs afterwards.
  • JIT compilation also benefits from Rice's Theorem since it imposes strong bounds on what static compilation can prove about the algorithm implemented.