Assisted Algorithms

  • Yuri Gurevich, University of Michigan; Nikolaj Bjørner, Microsoft

Algorithms are inherently deterministic. Here is a famous non deterministic algorithm: “When you come to a fork in the road, take it,” by Yogi Berra, the American baseball player and unlicensed philosopher, In our view, “nondeterministic algorithm” is a contradiction in terms. Yet there are useful probabilistic and quantum algorithms that are inherently non deterministic. How do they work? Our thesis is that non-algorithmic work — from tossing a coin to quantum measurement — is done by assistants, partners, oracles. We present the theory of assisted algorithms. Our running example is quantum, but no knowledge of quantum computing is assumed.

Watch Next