Entscheidungs Problem

Basically, the problem of determining whether or not two Boolean functions (functions returning boolean values) are equivalent--ie for functions A and B with domain S, and forall t in some set S, if A(t) == B(t).

Independently proven to be undecideable by both AlanTuring and AlonzoChurch.

As usual, Wikipedia has much more info.

See http://en.wikipedia.org/wiki/Entscheidungsproblem