The Algorithm Is Deterministic by Nature: Yuri Gurevich on Auxiliary Computation

In computer science, the word "algorithm" is often prefixed in various ways: probabilistic algorithm, quantum algorithm, non-deterministic algorithm. But Microsoft Research scientist Yuri Gurevich, in a recent talk, put forward a counterintuitive core thesis: a true algorithm is always deterministic. What is called "non-determinism" is merely the result of an algorithm obtaining information through external "assistants."

This view stems from his decades of research on the theory of Abstract State Machines (ASM). This article, based on the talk, lays out his argumentative logic, key concepts, and historical context.

The Algorithm Was Once Synonymous with Determinism

Gurevich reviewed the work of logicians from the 1930s to the 1950s. The core task at the time was to precisely characterize "effective method," which was eventually renamed "algorithm." In this tradition, determinism was part of the definition, not an added property.

He used a geometric algorithm as an example: from a point outside a circle, there are two tangents to the circle. A classic algorithm handed down from the Middle Ages can help you find the tangent lines, but the algorithm itself does not choose—the choice belongs to the person. The algorithm is only responsible for executing determinate steps; human intervention happens outside the algorithm. For this reason, Gurevich wrote in an early paper on abstract state machines that "non-deterministic algorithm" is a self-contradictory expression.

Later, things seemed to change. Probabilistic algorithms, quantum algorithms, and non-deterministic algorithms appeared one after another, and people assumed that the concept of algorithm had been broadened like an expansion of number systems. But Gurevich says he recently realized the situation is not so simple: these new species are not algorithms themselves becoming non-deterministic; rather, algorithms have learned to "ask for help."

The Turing machine is the central model for understanding this deterministic tradition: it consists of an infinite tape, a read/write head, and a finite state transition table, and every step (writing a symbol, moving the head, switching state) is uniquely determined by the current state and the symbol read. The Church-Turing thesis further claims that any function computable by an "effective method" can be computed by a Turing machine, which firmly binds "algorithm" to "deterministic mechanical steps." It is against this background that early logicians regarded non-determinism as a vagueness to be eliminated rather than a legitimate variant of an algorithm.

Computer Science Is the Science of Algorithms

In 1982, Gurevich moved from mathematics to computer science. He asked a fundamental question: as a science, what is the object of study of computer science? It is not like physics studying atoms or chemistry studying molecules. His conclusion: the core object of computer science is the algorithm.

A database is a certificate rather than an algorithm, but an operating system is essentially a scheduling algorithm, and a programming language is itself an algorithm—input a program, input data, execute. If this judgment holds, then "what is an algorithm" becomes a foundational question.

He also expressed dissatisfaction with the logical style of the time: declarative approaches such as denotational semantics and algebraic methods seemed like logicians lecturing programmers on what to do. But programmers are changing the world, and logicians have no moral right to preach to them. Gurevich wanted to understand what programmers were doing right—programmers do not write a piece of text to explain an algorithm; they program directly and run it directly. This led him toward executable high-level specifications, namely abstract state machines.

Three Postulates: From States to Interaction

The axiomatization of abstract state machines went through a long process. Gurevich summarizes it as three postulates, and the third took about 15 years to take shape.

The first postulate is a revised version of the sequential-time postulate. An algorithm is viewed as a transition system: a set of states, a set of initial states, and a set of steps for each state. After interaction is introduced, a step is no longer a simple function, because different steps may reach the same successor state yet have different externally observable interaction behavior. Termination is also no longer a property of states but of steps—after a step terminates, it reaches a "dead state" and does nothing further.

The second postulate draws on Tarski's model-theoretic tradition. A state is a logical structure, a function interpretation over a fixed vocabulary. A step is a "hook" carrying interaction content: each step records the log of messages the algorithm sends to interaction objects. There are two kinds of interaction objects: an oracle returns a response, while a recipient only receives messages and does not respond.

The third postulate (the bounded-exploration postulate) addresses the intuition that "an algorithm only looks at finite information." Each step corresponds to a bounded set of terms (tags), and the algorithm explores these terms according to a partial order; differences between two states are detected only if some Boolean term takes different values. If two steps agree on the Boolean terms, their termination states and state changes also agree.

A "logical structure" in the model-theoretic sense consists of a domain (a set of individual objects), a vocabulary (function symbols, relation symbols, and constant symbols), and the interpretation of these symbols over the domain. Treating algorithm states as such structures has the advantage that the internal representation of a state need not depend on a specific data structure; one only needs to care about which terms take which values under which interpretation. Tarski's definition of truth makes "a certain Boolean term is true in this state" a precise concept, and this is also the premise that allows the bounded-exploration postulate to characterize state differences in terms of "Boolean terms taking different values."

Rewriting Probabilistic and Quantum Algorithms with "Assistants"

The most striking part of the talk is the reformulation of probabilistic and quantum algorithms as deterministic algorithms plus external assistants.

Take a simplified Fermat primality test: repeat k times, each time randomly choose a, and if a^(n-1) mod n ≠ 1 then return composite. Traditionally this is a probabilistic algorithm. But Gurevich's rewrite is: the algorithm itself deterministically calls an oracle named choose in, asking it to choose a number between 1 and n-1. How the oracle chooses, and whether it is truly random, is the oracle's business, not the algorithm's.

The same goes for quantum algorithms. Take Grover's search algorithm: in the quantum circuit representation, operations such as Hadamard gates and unitary transformations are, for the algorithm, merely oracle calls that return true—they change the quantum state as a side effect, but the quantum state is invisible to the algorithm. Only the final measurement gate produces an observable 0/1 output. What the algorithm sees is deterministic control flow: repeat m times, increment the counter, and finally output n bits in parallel.

Gurevich admits that he is almost a layman in quantum physics. But mathematically, the linear algebra used in quantum computing is not mysterious; even the Heisenberg uncertainty principle, in his formulation, is merely a lemma of linear algebra. The mathematics is simple; the physical interpretation is the hard part.

The oracle concept originates from Turing reducibility in computability theory: a Turing machine can query an external black box in one step and obtain the correct answer without computing the problem itself. Classical results such as relativization proofs show that the existence of oracles changes the landscape of computability and complexity. Gurevich borrows this device in a different way: he does not care whether the oracle is computable, but uses it as an abstraction of an interaction object, packaging the effects of randomness sources or quantum gates outside the algorithm definition through "query-response," thereby preserving the determinism of the algorithm itself.

Spec Explorer and an Antitrust Case

Beyond theory, the talk also includes an industrial episode. In the late 1990s, Gurevich formed a team at Microsoft Research and developed Spec Explorer—a high-level executable specification tool based on abstract state machines. The work of team members such as Wolfgang Grieskamp made the tool robust.

Two kinds of people became users. The first were testers. At the time, testing positions had low status and poor pay, and developers were unwilling to communicate with them. Spec Explorer enabled testers to ask questions proactively and construct tests proactively. The second were senior managers, including Bill Gates. According to Gurevich, after listening for a few minutes, Gates asked: "How is this different from a Turing machine?" He then grasped the point and even helped explain it to his entourage.

The real turning point came from the European Union. Microsoft was sued by the EU and lost because a special protocol used in Windows gave internal programs more direct access than third parties. The EU required Microsoft to hand over high-level executable specifications rather than source code. Spec Explorer thus moved to center stage, and hundreds of engineers (mostly in China and India) used it to write protocol specifications.

Gurevich commented that this moment put formal modeling at the center of the most important regulatory battle in software history. However, he also admitted that the EU's victory was in some sense a Pyrrhic victory—new developments such as cross-platform tools made the whole situation obsolete.

Implications: The Assistant Model as a Cognitive Framework

Gurevich's argument is more than a terminological distinction. It provides a framework for viewing computing systems: externalize the source of uncertainty as an interaction object, keep the algorithm core deterministic, and let system behavior be determined by the collaboration between algorithm and assistant.

This resonates with the "external environment" approach in distributed systems, human-computer collaboration, and even tool calling in large models. The algorithm does not predict the environment; it only sends requests, receives responses, and proceeds under deterministic rules. How the assistant works internally is a question at another level.

Of course, the cost of this framework is that the algorithm's behavioral guarantees depend on assumptions about the assistant's behavior. The reliability of the Fermat test depends on the quality of the randomness source, and the correctness of a quantum algorithm depends on whether the quantum gates work as expected. Gurevich does not avoid this; he simply insists that these assumptions lie outside the algorithm definition.

For today's AI and computing practitioners, this perspective is worth pondering. When we say an AI system "has uncertainty," is the model itself uncertain, or are we treating the sampler, tool calls, and environmental feedback as part of the system? Where we draw the boundary determines how we define, test, and trust a system.

In distributed systems, this idea corresponds to treating the network, clocks, and failure models as environmental assumptions rather than part of the protocol logic; in reinforcement learning, the environment is formalized as an external interaction object that provides observations and rewards; in large-model tool calling, function return values are treated as responses from an external oracle. The common point is that the core control flow remains decidable and reproducible, uncertainty is pushed outside the interface, and it is recorded and verified in the form of explicit assumptions.