Assisted Algorithms

Yuri Gurevich argues that algorithms are inherently deterministic and that probabilistic and quantum algorithms work by delegating non-algorithmic steps such as coin flips and quantum measurements to external oracles or assistants. He presents a theory of assisted algorithms with revised abstract state machine postulates, using a primality test and Grover's search as running examples.