Excellent question! We call those "probabilistic Turing machines", and the most interesting complexity classes associated with them are ZPP and BPP. ZPP contai

Excellent question! We call those "probabilistic Turing machines", and the most interesting complexity classes associated with them are ZPP and BPP. ZPP contains problems for which the answer is guaranteed to be correct, and the machine halts in expected polynomial time -- the so-called "Las Vegas" algorithms. And then there's BPP, containing algorithms which always run in polynomial time but whose outputs have a constant, bounded probability of being wrong -- the "Monte Carlo" algorithms. Currently, we know that P ⊆ ZPP ⊆ BPP, but we haven't yet proved whether or not any of those classes are equal to each other. However, there's apparently mounting evidence -- most of which goes over my head -- that in fact P=BPP; in other words, any randomized algorithm can be "derandomized" with the use of a sufficiently strong pseudorandom number generator.