Non-deterministic Turing machine which chooses between the available transitions at each point according to some probability distribution