The study of nonprobabilistic computations employed the abstract models of deterministic and nondeterministic Turing transducers. For the study of probabilistic computations we will use similar abstract models, called probabilistic Turing transducers. Informally, a probabilistic Turing transducer is a Turing transducer that views nondeterminism as randomness. A sequence C of the moves of M is said to be a computation if the two conditions below hold.
C starts at an initial configuration.
Whenever C is finite, it ends either at an accepting configuration or a nonaccepting configuration from which no move is possible. A computation of M is said to be an accepting computation if it ends at an accepting configuration. Otherwise, the computation is said to be a nonaccepting , or a rejecting , computation . By definition, a probabilistic Turing transducer might have both accepting computations and nonaccepting computations on a given input. Each computation of a probabilistic Turing transducer is similar to that of a nondeterministic Turing transducer, the only exception arising upon reaching a configuration from which more than one move is possible.