Abstract
An earlier paper gives an account of a quest for a satisfactory
formalization of the classical informal notion of an algorithm.
In this paper, an attempt is made to generalize the results of that
quest to the notion of a probabilistic algorithm, i.e. an algorithm
that expresses a pattern of behaviour in which probabilistic choices
occur.
The central notions in this paper are the notion of a probabilistic
proto-algorithm and the notion of algorithmic equivalence of
probabilistic proto-algorithms.
Probabilistic algorithms are considered to be equivalence classes of
probabilistic proto-algorithms under algorithmic equivalence.
This means that the notion of a probabilistic algorithm is explained
without using any particular machine model or algorithmic language.