This definition seeks to formalize the intuitive characterization of a problems decidable by a probabilistic algorithm as one for which there exists a decision procedure which can make undetermined choices during its computation but still solves the problem correctly in a ‘clear majority’ of cases (i.e. with probability \(p\) bounded away from \(\frac{1}{2}\)). It is not difficult to see that if we possessed an algorithm for deciding \(X\) which is implementable by a machine \(C\) satisfying (i)–(iii), then we could correctly decide whether \(x \in X\) with arbitrarily high probability by applying the algorithm repeatedly and checking whether the majority of its computations accepted or rejected.[34]