* They are just like the state machines * Thus, given a set of inputs, 3 things can happen: success, failure, no reply * Hard problems are in this last category; they take a really, really long time to solve