Deterministic Computation

A bank runs payroll for tens of thousands of people, and nobody checks the arithmetic.

The system was tested once, years ago, and every run since has been trusted without a second look. It's the same with the query that totals last quarter's revenue, the code that moves money between accounts, and the formula filled down a hundred thousand rows of a spreadsheet.

We trust software like this with critical work and stop checking it constantly.

That's the only practical way to use it.

It's worth explaining why, because this idea is the foundation for everything that follows in this series of articles. Classical computing has a property we rely on constantly and almost never name: it is deterministic, and because it is deterministic, it can be checked.

If you understand both what it provides and what it requires, you'll have a way to judge everything that follows—especially the machines that lack those properties.

It Doesn't Guess. It Calculates.

Deterministic means the output is determined entirely by the input and the rules. Nothing else affects the result. The same input and the same rules always produce the same answer, on any machine that executes those rules correctly. The time of day doesn't matter. The operator doesn't matter.

The wording of the request doesn't matter.

Alan Turing pinned this down in 1936.^[9] His model of a computer is a machine with a fixed rule that looks at its current state and the symbol in front of it and decides, with no room for choice, exactly what to do next. There is no interpretation anywhere in the loop. As far as anyone has ever shown, that covers everything we mean by computation: whatever a person could work out by following fixed steps with pencil and paper, a machine like this can work out too.

Donald Knuth's definition of an algorithm makes the same demand from the engineer's side^[4] — every step spelled out exactly, with nothing left to interpretation.

That's what makes algorithms work.

The moment a step needs interpreting, you've left this kind of computation behind. (Real systems can wobble: threads race, floating-point rounds, someone adds randomness on purpose. Engineers treat those as problems to control, precisely because determinism is the thing they're trying to keep.)

All of this assumes a closed, tidy world: fixed types, a known set of symbols, a finite set of states laid out ahead of time. Inside that world there is nothing to interpret. SELECT SUM(revenue) FROM sales WHERE region = 'NE' has exactly one answer, set by the data and the meaning of the query — producing no ambiguity and needing no outside knowledge.

And beyond that, there is no judgment required between the question and the answer.

One point is worth making clearly, because everything that follows depends on it: deterministic is not the same as correct. A payroll formula with the wrong tax rate will produce the same wrong answer every time, perfectly reliably. Determinism doesn't give you the right answer. It gives you an answer that stays the same long enough to check.

That turns out to be worth a great deal, but determinism isn't free.

Why You Can Check It Once and Trust It

Determinism turns trust from an ongoing cost into a one-time investment. Once you've established that the system behaves predictably, you no longer have to keep watching it. It works for three reasons, all of them depending on one fact:

the answer stays the same.

Because you get the same result every time, you can debug it. You can rerun the program, compare the output, trace it back through its execution, identify the exact input that caused the problem, and reproduce the bug whenever you need to. A bug you can reproduce is a bug you can fix. It also means another engineer—or even the same engineer a year later—can verify exactly what happened.

When the problem is small and well-defined enough, you can go further and prove the code correct. Tony Hoare showed in 1969 how to do this as a matter of logic^[2]: state what is true before the code runs and what must be true after, then derive whether the program delivers. This isn't only theory. A security microkernel called seL4 ships with a machine-checked proof that its code matches its specification.^[3]

Formal verification is expensive and can't be applied to every system. But where it's practical, it provides a guarantee that no amount of testing can match.

Most of the time, you don't prove software correct—you test it. You run the code against cases with known answers and compare the results. Because the software is deterministic, the same test catches the same bug every time. A test suite that passes today will pass tomorrow for the same reasons.

Put these ideas together, and you get a rule that every engineering organization follows, whether they say it explicitly or not: verify the system once, then trust its output. The careful, expensive review happens only once—when one engineer writes the rules and another verifies them. Every execution after that inherits the result. From that point on, oversight shifts to maintenance. Engineers watch for changing requirements, software defects, or bad input data—not arithmetic mistakes, because a deterministic system cannot introduce those on its own. That's why no one recalculates payroll by hand. It's not blind faith or carelessness.

The system was verified once, and determinism ensures that each run produces the same result.

What Even This Machine Can't Do

None of this makes the machine all-knowing about itself. And its limits aren't problems that a better tool will solve. They were proven decades ago, and they are permanent.

Turing's other famous result is the halting problem^[9]: there is no general algorithm that can examine an arbitrary program and its input and determine whether the program will ever stop. This isn't a matter of speed. There is no such algorithm at all. Some questions about programs simply cannot be answered algorithmically.

Henry Rice generalized that in 1953.^[7] Ask any real question about what a program does — not how it's written, but what it computes: does it always halt, does it return the right answer on every input, could it ever crash on a null pointer — and no single algorithm answers it for all programs.

That's why static analyzers and type checkers work the way they do.

They don't try to answer the impossible general question. Instead, they answer a narrower question that can be decided reliably.

The everyday version is a line most programmers eventually hear, from Edsger Dijkstra^[1]: testing can show that bugs are present, never that they're absent. A passing test tells you the code worked on the inputs you tried and nothing about the ones you didn't. If a finite set of tests could prove a program fully correct, that impossible general question would be answerable.

There's a second fundamental limit.

Even a change you know is correct raises the question of what else it touches, and John McCarthy and Patrick Hayes showed — they called it the frame problem^[5] — that listing everything an action leaves alone has no natural end.

Rice's theorem says there is no general algorithm for determining what an arbitrary program does. The frame problem says there is no general way to identify all of a system's relevant consequences.

None of this makes deterministic computing less valuable. It simply defines its limits.

Deterministic systems give you results you can reproduce, test, and verify. For well-defined problems, they can even provide mathematical guarantees. What they cannot do is provide a general method for determining what any program means or predicting every consequence of its execution. Those decisions have always belonged to people—to the engineers who define the specification, choose the tests, and decide what the system is meant to accomplish.

Why It Works: A Closed World

Why does all of this work? Because classical computing is built on a closed world.

Claude Shannon laid the floor in 1948.^[8] By defining information as a fixed set of discrete symbols, Shannon made it possible to encode information exactly and recover it reliably—even over a noisy communication channel. Below a certain transmission rate, the error can be made arbitrarily small. That's why a bit is a bit. Digital computers are built on a foundation where information can be copied, stored, and transmitted without ambiguity or loss.

On top of that substrate, a computer shuffles symbols according to fixed rules — Allen Newell and Herbert Simon's way of describing it^[6]. Whatever cleverness runs on top, the base is exact and deterministic, and that base is the part you can verify.

The idea that makes all of this work is simple: everything the system needs to know is defined before it runs.

The symbols are fixed, the possible states are known, and the rules are complete. Under those conditions, the system is trustworthy by construction. Determinism, reproducibility, and formal verification all follow from a world that has been fully specified in advance. The real question—and the one this series explores—is what happens when those conditions no longer hold.

What Happens When the World Opens Up

Point software at open-ended language instead of structured data and every one of these guarantees falls away at once.

It is no longer deterministic. Ask the same question in slightly different words, and you may get a different answer—not just a different wording of the same answer. It is no longer reproducible, so there is no stable result to compare against and no failure you can reliably reproduce. And the world is no longer closed. The meaning of a sentence is not contained entirely within its words;

the reader brings context that was never written down.

And there's no specification to check the output against, because the machine isn't following inspectable rules. It produces whatever looks most plausible next.

This is the key idea, and the reason we've compared these two kinds of machines.

Deterministic computing has real limits, but they're about general questions across all possible programs. Any single run still reproduces, and you can still check it against a fixed answer.

Open-ended language computation loses even that.

The individual output won't reproduce and can't be checked against anything stable, and the "check once + trust" deal never becomes available. The oversight that determinism made a one-time cost turns back into a cost you pay on every output.

This article establishes the baseline of traditional deterministic computation. Future articles examine what these differences mean for the work and for the people responsible for checking it.

The Machine We Trust Without Watching

Deterministic computing is the machine we learned to trust without watching. It follows fixed rules in a closed world, produces the same result every time, and once verified, stays verified. It has fundamental limits—questions that no algorithm can answer—but within those limits, its guarantees are real.

Everything that follows in this series about risk, effort, and human judgment is measured against this baseline.

To understand why today's language models are different in kind, not merely less mature, you first have to understand what deterministic computing actually promises. This is that promise. The rest of the series is about what happens when you give it up.

---

References

1. Dijkstra, E. W. (1970). Notes on Structured Programming (EWD249). Technological University Eindhoven.
2. Hoare, C. A. R. (1969). An axiomatic basis for computer programming. Communications of the ACM, 12(10), 576–580.
3. Klein, G., et al. (2009). seL4: Formal verification of an OS kernel. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles (SOSP '09), pp. 207–220. ACM.
4. Knuth, D. E. (1968). The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley.
5. McCarthy, J., & Hayes, P. J. (1969). Some philosophical problems from the standpoint of artificial intelligence. In B. Meltzer & D. Michie (Eds.), Machine Intelligence 4 (pp. 463–502). Edinburgh University Press.
6. Newell, A., & Simon, H. A. (1976). Computer science as empirical inquiry: Symbols and search. Communications of the ACM, 19(3), 113–126.
7. Rice, H. G. (1953). Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society, 74(2), 358–366.
8. Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27, 379–423, 623–656.
9. Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2(42), 230–265.