We cited Church's Thesis in Section: every "algorithm" (in the heuristic meaining of the word) is realizable on a Turing machine. It turned out that other models of computation were able to solve exactly the same class of problems.
But there is an extension of the notion of an algorithm that is more powerful than a Turing machine, and still realizable in the real world. This is the notion of a randomized algorithm: we permit "coin tossing", i.e., the have access to a random number generator. Such machines will be able to solve problems that the Turing machine cannot solve (we will formulate and prove this in an exact sense in a later section); furthermore, such machines can solve some problems more efficiently than Turing machines. We start with a discussion of such examples. The simplest example of such an application of randomization is checking an algebraic identity; the most important is quite certainly testing whether an integer is a prime.
Since in this way, we obtain a new, stronger mathematical notion of a machine, corresponding randomized complexity classes can also be introduced. Some of the most important ones will be treated at the end of the section.