Compiling the Trap

Sun, 17 May 2026

This is a follow-up to Shifting the Trap and to Jacob K's Writing custom programs for yt-dlp's jsinterp.

In Shifting the Trap, I argued that yt_dlp/jsinterp.py is, despite the hedging, a real interpreter for a subset of JavaScript - and that an interpreter faithfully executing a non-free, Google-authored program (base.js) is The JavaScript Trap, merely relocated from the browser to the terminal.

Jacob K then went further, empirically, and hand-wrote Fibonacci and a Rule 110 simulator in JSinterp's language and observed them run. The conclusion: at some point, enough machinery accreted - for, switch, arrays - that the interpreter became Turing-complete. This left an explicit open question: which release crossed that line, and can it be shown rigorously rather than anecdotally?

This post closes the loop with a constructive proof. Not "here's a program that looks Turing-complete," but: here's a compiler whose target is yt-dlp's interpreter, and here's the formal reduction that makes its existence a proof.

That compiler lives in https://jxself.org/git/?p=bfc.git.

Why does a compiler prove anything?

Turing-completeness is a statement about a computational class. The clean way to establish it for a system S is a reduction: exhibit a language T already known to be Turing-complete, and a total translation compile: T → S that preserves observable behavior. If every T-program can be mechanically turned into an S-program that computes the same thing, then S can compute everything T can, which is everything. So the question is only: which T?

I briefly thought about a C compiler, but that would be enormous. Turing-completeness isn't about whether the language is pleasant, only about what it can compute. The right T for this demo, then, is the smallest language known to be Turing-complete. That's Brainfuck - eight commands, a tape, and a loop; reducible to and from a Turing machine by a well-known construction.

Brainfuck also happens to map onto precisely the part of jsinterp that is oldest, most exercised, and least likely to hide a bug - the same machinery Jacob K's programs already leaned on. That's not a coincidence; it's the point. The proof should rest on jsinterp's load-bearing wall, not its experimental trim.

The compiler: bfc.py

compile_bf is about sixty lines and imports nothing from yt-dlp. It's a total function from Brainfuck source to a single JavaScript function, written against the intersection of JavaScript and what jsinterp actually implements:

+ -	t[p]=(t[p]+1)&255; - & 255 gives mod-256 cells; jsinterp's bit ops use Python &, so (0-1)&255 == 255, the correct Brainfuck wrap
> <	p=p+1;
. ,	o=o+String.fromCharCode(t[p]); / a ternary read from the input array
[ ]	for(;t[p]!=0;){ … }

The one load-bearing trick is the loop. jsinterp has no while, so Brainfuck's [ ] becomes a for with empty init and increment whose guard re-reads the current cell. Nested Brainfuck loops are just nested fors. The guard uses loose != (jsinterp's equality-coercion path), deliberately not !== (which is Python is-identity and unsafe across all cell values).

Nothing in the output recurses. Brainfuck loops compile to JavaScript loops, so the proof never touches jsinterp's ~100-deep recursion budget. The compiler also coalesces runs of +/> into a single statement - the textbook Brainfuck optimization, observationally identical, included only to prevent the regex-walking interpreter from re-parsing thousands of one-character statements.

The demonstration: run_proof.py

Each program is compiled and then executed by the real, unmodified yt_dlp.jsinterp.JSInterpreter - the same class, reached the same way (JSInterpreter(code).call_function(...)), that decodes YouTube's signatures - and its output is checked against an independent Python oracle.

Hello World - the canonical Brainfuck program. Loops and I/O, exact output. Sanity.
Unary echo - output n asterisks, where n comes from the input. This matters: the iteration count is data-dependent and determined at runtime, not baked into the program text. Straight-line code can't do this; an interpreter with genuine loops can. It's the smallest honest witness that the [ ] → for lowering does real, unbounded work.
Rule 110 - Cook's elementary cellular automaton, proven Turing-complete, and the very automaton Jacob K simulated on older jsinterp. Width is fixed; the number of generations comes from input, so the outer loop is again data-dependent. Every generation is checked, cell by cell, against a pure-Python implementation of Rule 110.

All pass, on the interpreter as shipped:

[PASS] hello world [PASS] unary echo n=0 / 1 / 5 / 23 [PASS] rule 110 (w=24, g=1 / 8 / 20) ALL PROOFS PASSED (on real yt_dlp.jsinterp)

Rule 110 from a single right-edge seed - the familiar fractal - emitted by yt_dlp/jsinterp.py and byte-for-byte equal to the oracle:

..............................## .............................### ............................##.# ...........................##### ..........................##...# .........................###..## ........................##.#.### .......................#######.# ......................##.....### .....................###....##.# ....................##.#...##### ...................#####..##...# ..................##...#.###..## .................###..####.#.### ................##.#.##..#####.# ...............########.##...### ..............##......####..##.# .............###.....##..#.##### ............##.#....###.####...# ...........#####...##.###..#..## ..........##...#..#####.#.##.### .........###..##.##...########.# ........##.#.######..##......### .......#######....#.###.....##.#

The honest caveat

The real interpreter has a finite tape and a finite recursion budget. The Turing-completeness of the model is unaffected: the reduction is total, and the limits are resource bounds, not expressivity bounds. This is the same footnote that applies to every physical computer, and the same one Jacob K reached for when noting that loop-unrolling in very old youtube-dl still satisfies the colloquial definition. Stating it plainly strengthens the claim rather than weakening it. The compiler is exact; the machine, like all machines, is merely large.

It also sharpens Jacob K's open question, though only in one direction. If the ladder passes on a given revision, that revision is Turing-complete - the compiler is the witness, contingent on its output being valid on that revision. The other direction does't follow: a failure means only that this particular compiler doesn't target that particular revision, not that the revision lacks Turing-completeness. Settling that in the negative needs either a different compiler or a direct argument about the language's expressivity.

Why this is the proof the argument needed

Shifting the Trap made a definitional claim: jsinterp is an interpreter. The natural rejoinder was "an interpreter of what, and how much?" If it could only pattern-match signature functions, one might argue that the freedom question is narrow. It cannot only do that. A faithful interpreter of a Turing-complete language is, by construction, a general-purpose execution engine: whatever Google ships in base.js, jsinterp will run, because there's no computable behavior it can't run. The signature dance isn't the ceiling; it's one program among all programs.

That's the technical spine of the original blog post. The trap was never "yt-dlp runs a specific clever string function." The trap is that a free program, in its normal operation, hands a non-free, Google-authored, daily-mutating program to a general-purpose interpreter on the user's machine and runs it. The compiler doesn't accuse yt-dlp of anything. It just removes the last place to hide the word "interpreter," and with it, the last reason to believe the question in the first post can be safely left unasked:

Whose program is running on your computer right now, and did you agree to run it?