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.
Yuri Gurevich opens by recalling his long history with the host and Microsoft Research, then argues that algorithms are inherently deterministic, so “nondeterministic algorithm” is a contradiction in terms. He traces how logicians in the 1930s to 1950s formalized effective methods, noting that Church’s thesis implicitly assumed a pure, clean initial state. In 1982 he moved from mathematics to computer science, arguing that computer science is fundamentally about algorithms, and that logicians had no right to lecture programmers who were already changing the world. This led him to abstract state machines (ASMs), a declarative-to-executable approach that matured through practical use, including the Spec Explorer tool, its role in a Microsoft-EU regulatory dispute over protocol transparency, and the Windows team’s adoption of it.
Algorithms, Assistants, and Oracles
The core thesis is that algorithms remain deterministic, but probabilistic and quantum algorithms delegate non-algorithmic steps (coin flips, quantum measurements) to external partners, which Gurevich calls assistants, interactants, or oracles. A coin flip cannot be computed algorithmically, so the algorithm simply subcontracts it and receives a result. Gurevich revisits his earlier work with Andreas Blass, which treated the environment as an opaque source of input, and says he now revised the three ASM postulates to account for interaction.
Running Examples
Two examples anchor the discussion. The first is a simplified Fermat primality test, which picks random bases and checks Fermat’s little theorem; a witness that fails the test proves compositeness, but passing only gives probable primality. The second is Grover’s quantum search algorithm, presented as a quantum circuit whose unitary gates act as oracles that simply return true as a side effect, while the quantum state remains invisible to the algorithm itself. Grover’s search finds one marked item among n in roughly the square root of n steps, which is optimal, and the quantum work is delegated to these oracle “demons,” whose coordination is described as glorified linear algebra.
The Revised Postulates
The sequential-time postulate now uses steps rather than terminal states, since termination itself may depend on interaction. Two different steps can lead to the same successor state yet produce different externally observable behavior, so nondeterministic transition functions alone are insufficient. The abstract-state postulate treats states as first-order logical structures, with steps producing logs of interaction messages (oracle queries with replies, or recipient messages with no reply). The bounded-exploration postulate, inspired by an abstract of Kolmogorov’s work on steps of bounded complexity, states that a bounded set of terms suffices to detect state differences, so steps that agree on those terms produce identical updates.
Representation and Open Questions
Gurevich shows that every algorithm has a corresponding ASM, and he presents the ASM code for the primality test with a choose oracle in place of random selection. He notes subtleties around halting and the universal simulation of algorithms that may report termination at arbitrary points. In the audience discussion, he clarifies that the quantum algorithm is an outer loop of a fixed number of rounds, with oracle failures causing early termination, and that quantum mechanics sits outside the ASM picture as external interactants.