 So far, the Turing machines we have been discussing have been deterministic; for such machines, their behaviour at any given time is wholly determined by their state plus whatever their input happens to be. In other words such machines have a unique “instruction table” (i.e. transition function). We can generalise the Turing model, however, by allowing a machine to instantiate more than one transition function simultaneously. A nondeterministic Turing machine (NTM), upon being presented with a given input in a given state, is allowed to ‘choose’ which of its transition functions to follow, and we say that it solves a given problem whenever, given some input, there exists at least one path through its state space leading to a solution. Exactly how an NTM “chooses” whether to follow one transition function rather than another is left undefined (in his 1936 paper, Turing originally conceived these choices as those of an external operator). In particular, we do not assume that any probabilities are attached to these choices. In a probabilistic Turing machine (PTM), on the other hand, we characterise the computer’s choices by associating a particular probability with each of its possible transitions.