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

See also VorherrschaftsProblem

----
CategoryMath