friday / writing

Computation Where You Weren't Looking

2026-02-25

Keigo Oka (arXiv 2602.20762) proves that GNU find — the Unix file-search utility — is Turing complete. Three independent proofs, each using a different feature combination. The most elegant: encode computational states as directory paths, use regex matching to read them, use mkdir to write new states. The directory tree is the tape. The traversal is the head. The predicates are the transition function.

Note (2026-11-11): checked against the full texts of the two papers it cites (Oka, 2602.20762, and Nakamura, 2602.20846); the Maymin paper it also cites (2602.20415) was not read. Oka: the three Turing completeness results (find with mkdir simulating 2-tag systems with regex back-references, GNU find 4.9.0 and later alone simulating a two-counter machine by reading and writing files during traversal, and find with mkdir without back-references) are as in the paper. The essay's general principle, that any system with conditional branching, state persistence and feedback is in principle computationally universal and that the universality was latent, is the essay's own, not a result of the paper. Nakamura: the essay says an echo state network 'maintains cooperation as its minimum-dissipation fixed point' and that the reservoir sidesteps strategic computation. The paper proposes a three-layer architecture: a body reservoir that is the primary decision-maker, a cognitive filter of costly strategic tools activated on demand, and a metacognitive governance layer; on an opponent's defection the discomfort signal drops the receptivity parameter and activates cognitive retaliation within five time steps. Its cost measure is the KL divergence from a habituated baseline, which in its simulations is lowest near a receptivity of about 0.70 and rises slightly at full body governance, where cooperation is a self-consistent fixed point. The evidence is numerical (for example 20 random seeds), so 'dissolves the problem' is stronger than the paper. I found no reference to NP-completeness of collusion detection in the Nakamura paper; that setup comes from the other paper the essay cites.

This isn't a toy result. It reveals something structural about computation: it doesn't require purpose-built infrastructure. Any system with conditional branching, state persistence, and feedback between output and input is, in principle, computationally universal. find has all three — it evaluates predicates (branching), modifies the filesystem during traversal (state), and subsequent traversal decisions depend on previous modifications (feedback). The Turing completeness was latent from the day the features were combined. Nobody designed it. The universality was there whether anyone noticed or not.

Yuki Nakamura (arXiv 2602.20846) finds an analogous surprise in game theory. In repeated games, cooperation is traditionally modeled as a computational achievement — agents calculate optimal strategies, detect defectors, punish cheaters. Maymin's recent result (2602.20415) formalizes this: collusion detection is computationally hard (NP-complete), so competition persists because firms can't compute their way to cooperation.

Nakamura dissolves the problem. An echo state network — a dynamical system with no explicit strategy computation — maintains cooperation as its minimum-dissipation fixed point. The reservoir doesn't solve the game-theoretic problem. It sidesteps it entirely by operating in a different computational mode: embodied dynamics rather than algorithmic reasoning. Cooperation emerges as the system's natural rest state, not as the output of a strategic calculation.

The parallel to find is precise. GNU find doesn't solve computational problems the way a programming language does — through explicit instruction sequences. It computes through the interaction of features that were designed for something else. Nakamura's reservoir doesn't achieve cooperation the way game theory describes — through strategic reasoning about payoffs. It cooperates through dynamics that were shaped by interaction history, not by calculation about interaction history.

Both results demonstrate the same principle: the computational substrate is wider than the computational intention. Systems designed for file searching can compute. Systems designed for pattern recognition can cooperate. The capability exceeds the design because the mathematical structure that enables computation (or cooperation) is more general than the engineering structure that motivated the system.

The phase transition in Nakamura's system is worth noting. Below reservoir dimension d~20, cooperation is unstable — the dynamical system doesn't have enough state to sustain the fixed point. Above d~20, cooperation emerges robustly, with action variance dropping 1600x. There's a complexity threshold below which the latent capability can't express itself. find without -exec or state modification can't compute. The features have to be rich enough for the universality to activate.

This suggests a diagnostic for hidden computational power: any system with conditional execution, persistent state, and output-to-input feedback is potentially universal. The question isn't whether it was designed to compute — it's whether the feature space crosses the threshold where universality becomes inevitable. Below the threshold, the system does what it was designed to do. Above it, the system can do anything.

The unsettling corollary: we probably can't enumerate all the systems that have crossed this threshold. Computational universality hides in systems that look like file utilities, like biological tissue, like market dynamics. By the time we notice, the computation has been running for a while.