Conao3 Notes

git fetch is Turing complete

This is a program:

$ git fetch loop

Git runs it from a .git/config that holds fetch refspecs, a remote group, and one include. git fetch renames a single ref again and again and stops when the computation ends. With the right config, git fetch computes anything a Turing machine can.

In October 2026, Nicolas Seriot showed that curl 8.12 to 8.16 could run a two-counter Minsky machine from its configuration files (How curl was accidentally Turing-complete for nine months). Git does the same with its own config and starts no hook or alias along the way. Claude Opus 5.5 found this construction, and the last section tells that story.

The code is at conao3/minsky-git. git-minsky compiles a small program into a repository, and plain Git runs it.

The big picture

Git uses four ordinary features as the four parts of a computer.

Part of a computer Git feature
Memory the name of a single ref
Instructions fetch refspecs, which rename refs by a pattern
Clock a remote group that contains itself, so git fetch restarts itself
Halt an include that breaks .git/config when a directory appears

The figure below shows a complete run of a program that doubles a = 3 into b. Each box holds the ref name after one step, and the columns on the right decode it into the current instruction and the two counters. Each step renames the ref. At halt, Git can no longer read its own config, and the fetch stops.

img

The figure shows a two-counter Minsky machine, and Minsky proved that this kind of machine can simulate any Turing machine.

The machine to build

A two-counter Minsky machine has two counters, a and b, that hold non-negative integers, and a numbered list of instructions of three kinds.

  • inc r next: add one to counter r and go to instruction next.
  • dec r next zero: if r is positive, subtract one and go to next; otherwise go to zero.
  • halt: stop.

examples/double.prog is the program in the figure. Instruction 1 takes one from a, instructions 2 and 3 add two to b, and the machine halts when a reaches zero.

1 dec a 2 H
2 inc b 3
3 inc b 1
H halt

On the Git side, I set one rule: the machine uses Git's own behavior and nothing that runs another program. Git can run programs through hooks, aliases that start with !, clean and smudge filters, diff drivers, core.editor, core.pager, and credential helpers, and the machine uses none of them.

Memory: one ref name

I store the whole machine in the name of a single ref.

img

refs/A/s3xaaybz means instruction 3 with a = 2 and b = 1. Each counter appears in unary between two markers: x and y enclose a, and y and z enclose b. An empty counter leaves two markers side by side, as in refs/A/s1xaaayz, where b = 0. All refs point at the same empty commit, and the machine reads their names alone. The two-fetch step below uses the slot A.

Instructions: refspecs are rewrite rules

The repository has a remote called self whose URL is ., the repository itself. A glob refspec such as +refs/A/s1x*:refs/B/s2xa* matches a ref name, keeps the part matched by *, and replaces the fixed text around it. A counter machine needs no more than that: it adds or removes one letter at either end of a counter and changes the instruction number.

Instruction Refspecs
1 inc a 2 +refs/A/s1x*:refs/B/s2xa*
1 inc b 2 +refs/A/s1x*z:refs/B/s2x*bz
1 dec a 2 3 +refs/A/s1xa*:refs/B/s2x* and +refs/A/s1xy*:refs/B/s3xy*
1 dec b 2 3 +refs/A/s1x*bz:refs/B/s2x*z and +refs/A/s1x*yz:refs/B/s3x*yz

Pattern matching gives the zero test. refs/A/s1xa* matches when a is positive, and refs/A/s1xy* matches when a is zero.

One step takes two fetches

The instruction refspecs read from refs/A and write to refs/B. self has one more refspec, +refs/B/*:refs/A/*, and remote.self.prune = true. A fetch from self sees the refs that existed before the fetch, writes every destination, and prunes the destination refs that no source produced. As a result, the ref moves to refs/B on one fetch and back to refs/A on the next.

img

One step of the machine takes two fetches from self, which is one arrow in the first figure.

Clock: a remote group that contains itself

Git can fetch a group of remotes with git fetch <group>, and a group may list itself.

[remotes]
        loop = self
        loop = loop

git fetch loop fetches self, then starts a new git fetch process for the group loop. Each new process does the same, and this chain of processes ticks the clock until the program halts. One git fetch loop from your shell runs the program to the end.

Halt: a broken include

The configuration ends with include.path = refs/H. Git resolves this path relative to .git/ and skips an include file that does not exist without an error.

The halt instruction writes one more ref, refs/H/<counters>, and the files ref backend creates the directory .git/refs/H to store it. Git then fails to read .git/config, the next nested git fetch exits with an error, and each parent process exits in turn.

The whole program

git-minsky compiles double.prog into the .git/config below. The gray labels on the left show which instruction each refspec implements.

img

I ran it with a = 3 and set two environment variables to keep my own Git configuration out of the experiment.

$ export GIT_CONFIG_GLOBAL=/dev/null GIT_CONFIG_NOSYSTEM=1
$ bin/git-minsky machine create-repository \
    --repository-path /tmp/m --program file://examples/double.prog --counter-a 3
{"RepositoryPath":"/tmp/m","Ref":"refs/A/s1xaaayz","RefspecCount":7}
$ git -C /tmp/m fetch loop
Fetching self
From .
 - [deleted]         (none)          -> refs/A/s1xaaayz
 * [new ref]         refs/A/s1xaaayz -> refs/B/s2xaayz
Fetching loop
Fetching self
From .
 - [deleted]         (none)         -> refs/B/s2xaayz
 * [new ref]         refs/B/s2xaayz -> refs/A/s2xaayz
...
warning: unable to access '.git/refs/H': Is a directory
fatal: bad config line 24 in file .git/config
error: could not fetch loop
...
$ bin/git-minsky machine describe-state --repository-path /tmp/m
{"State":"H","CounterA":0,"CounterB":6,"Halted":true}

The fetch log doubles as the execution trace. Each [new ref] line records one rename, and its refs/A names match the boxes of the first figure.

Limits

Like the curl construction, this one is Turing complete with unbounded resources, and a real machine sets these limits.

  • Each step nests two more git fetch processes. On my Linux machine, a program that never halts died after 1,812 fetches (three minutes) with unable to fork and Argument list too long.
  • The files ref backend stores a ref as a file, so a ref name has at most 255 bytes, and a + b has to stay below about 250. The reftable backend removes that limit, but the halting trick needs the files backend.
  • For a local URL, Git starts git-upload-pack through /bin/sh -c. That shell runs one command, git-upload-pack, as a process outside Git.

Security impact

I see none. The program sits in .git/config, and git clone leaves that file behind, so a remote repository has no way to plant it. A remote sends refs and objects, and your local refspecs decide what happens to their names. Anyone who can write .git/config can run any command through core.hooksPath or an alias that starts with !, as the SECURITY section of git(1) states. At worst, this construction fills the machine with nested git fetch processes, and the person who wrote the config could do that with a shell loop too.

How Claude Opus 5.5 found it

I asked Claude Code, in Japanese, whether there were other stories like curl being Turing complete. Opus 5.5 answered with the well-known list, from sed and sendmail.cf to Magic: The Gathering and GNU find. Then I asked it to find new examples, since people on the internet love this kind of thing, and a moment later I added "use agents while you explore". Those two messages made up the whole brief.

Opus 5.5 began by screening dozens of everyday tools for the three things curl had: state it can rewrite, a way to branch, and a way to repeat, all without a shell. Most tools fail the third test. ssh_config caps its include depth, Prometheus relabeling runs each rule once, and Terraform rejects a module that calls itself. tmux passed all three, but willhbr proved it Turing complete in 2024, so Opus 5.5 dropped it.

Opus 5.5 gave each of the two survivors its own agent.

  • Web server rewrite rules. Apache's [N] flag restarts the rule set after each rewrite, so the rules form a string rewriting system. The same agent took nginx.
  • Git. Its configuration has includes and conditions, and its refspecs rename refs.

A third agent took everything else, with orders to list more candidates, screen them the same way, and build the best one. All three agents followed the same rule: use the tool's own features, with no shell escape or embedded scripting language, and run the result.

The Git agent tried the obvious parts of Git first and found that each lacked writable state, a loop, or both.

  • include.path and includeIf read configuration and cannot change it, and Git stops at an include depth of 10.
  • Aliases without ! expand to one Git command, and Git detects alias loops.
  • The todo list of git rebase -i moves forward and cannot jump back. label and reset move HEAD but not the position in the list, and a conflict stops the rebase, so the list cannot branch.
  • Revision syntax, for-each-ref --format with %(if), and mailmap read state and cannot write it.

Fetch refspecs let Git read a name, rewrite it by a pattern, and write it back, and a remote group adds the loop. About fourteen minutes after it started, the agent reported a working two-counter Minsky machine, the measured recursion limit, and the caveat about /bin/sh.

The other two agents also reported back. Apache's mod_rewrite worked too, but s3lph had built a binary adder with it in 2020. nginx stops after 10 rewrites, and only a rebuild changes that limit. The third agent made ImageMagick compute Rule 110 in a single magick command and confirmed that GNU units rejects recursive definitions.

I asked whether any of this was new. Opus 5.5 searched again and reported the prior art it found, such as the mod_rewrite adder. It found no prior art for the Git construction; a search can miss things, so if you know of earlier work, please tell me. Opus 5.5 also wrote git-minsky, its tests, and the first draft of this post. Each command output in this post comes from a real run, pasted as is.