The Turing Completeness of FFmpeg Filters.
12 Apr 2026

In my webcam entropy blog post, I found a use case for the FFmpeg geq video filter. In exploring the source code, I developed a hunch that the FFmpeg video filter may be Turing-complete.

TLDR

It is widely accepted that “Rule 110” according to Wolfram’s notation is a Turing-complete elementary cellular automata. This post shows how I implemented this cellular automata with FFmpeg video filters (and a bit of Bash).

Let’s assume each pixel in a size \(n\times 1\) video represents a cell in a cellular automata. Each pixel can hold one of two values. The fundamental challenge is that (as far as I know) FFmpeg filters cannot recursively affect frames. That is, pixels modified by a unique filter cannot be modified again by the same filter. This eliminates using the vertical spatial dimension as the “working history” of the cellular automata. Likewise, it eliminates using the temporal dimension (one frame for each iteration). So unfortunately, we have to accept FFmpeg may only apply the rule once, and we will have to rerun the command to do anything meaningful.

The general approach takes place in Bash:

  1. We begin with a Bash string in hexadecimal.
  2. The string is converted to a binary file with xxd
  3. FFmpeg applies Rule 110 to the file
  4. Optionally, the binary file is dumped and appended to a log
  5. Repeat. Go back to 2.

Input string #

Step one is completely arbitrary. I am choosing a simple input:

str=$(printf "%010d" 1)
str+="00"
# output is `000000000100`

It is important to remember that str is to be interpreted as hexadecimal, not binary.

Bash string to binary file #

Now, we convert to a binary file called input0:

echo -n $str | xxd -r -p > input0

FFmpeg command #

For FFmpeg to interpret these bits as individual pixels we need a few things.

  1. The pixel format must have one bit per pixel.
  2. The video format must be rawvideo
  3. The frame dimensions must be specified

To satisfy the first requirement, two options exist. I’m using monob, a pixel format where a 0 bit is interpreted as black and a 1 bit is interpreted as white. The third requirement requires knowing how many bits are in the file. I do this with the bash:

num_bits=$(( $(wc -c < $input) * 8 ))

Which gets the number of bytes with wc then returns the result times 8. Now, we can say there will be only one frame in the “video” and set the size with the FFmpeg flag -s "${num_bits}x1".

So far, our command looks something like this

ffmpeg -f rawvideo -pix_fmt monob -s "${num_bits}x1"\
    -i $input -vf ... $output

with the video filter -vf to be completed.

No true bitwise operations :( #

Unfortunatly, I could not get the geq filter to work right with the monob format, so the first step is converting the pixel format to gray, where now 8 bits go to each pixel. Suppose I simply wanted to perform a logical NOT operator on the bits; the filter becomes

-vf "format=gray,geq=lum='not(p(X,Y))*255',format=monob"

At first this seems wasteful, but just recall what the purpose of this project is. What we are doing in the above filter is converting (casting?) each pixel to be unsigned 8-bit integers by padding zeros. Then, we do the geq NOT operation which sets the output to 0 when the input is non-zero, and 1 otherwise. This is why we must multiply by 255 at the end, so that the conversion back to 1-bit (monob) works. Otherwise, both 0 and 1 in gray format get mapped to 0.

Implementing Rule 110 #

Checking WolframAlpha, this rule has an algebraic form, which is what I will be using. Given three adjacent pixels as the ordered tuple \((p,q,r)\), the next generation is given by the map \(f:(\mathbb{F}_2)^3\rightarrow \mathbb{F}_2\):

$$(p,q,r)\mapsto (q+r+qr+pqr)\pmod{2}$$

where the modulo serves a reminder that the result should be either 0 or 1. For a given pixel, this means the filter should do

mod(p(X-1,Y)*p(X,Y)*p(X+1,Y)+p(X,Y)*p(X+1,Y)+p(X+1,Y)+p(X,Y),2)

So all together, the FFmpeg command looks like this:

ffmpeg -f rawvideo -pix_fmt monob -s "${num_bits}x1" -i $input \
    -vf "format=gray,geq=lum='mod(p(X-1,Y)*p(X,Y)*p(X+1,Y)+p(X,Y)*p(X+1,Y)+p(X+1,Y)+p(X,Y),2)*255',format=monob"\
    -f rawvideo $output

And that’s really it. \(\blacksquare\)

Test #

If you want to see for yourself, here’s the bash script you can use:

#!/usr/bin/bash

num_iter=28
str=$(printf "%010d" 1)
str+="00"
echo -n $str | xxd -r -p > input0
xxd -b input0 > output.log

for i in $(seq 0 $num_iter); do
    ifile=$(printf "input%d" $i)
    ofile=$(printf "input%d" $(( i + 1 )))

    num_bits=$(( $(wc -c < $ifile) * 8 ))
    ffmpeg -f rawvideo -pix_fmt monob -s "${num_bits}x1" -i "$ifile"\
        -vf "format=gray,geq=lum='mod(p(X-1,Y)*p(X,Y)*p(X+1,Y)+p(X,Y)*p(X+1,Y)+p(X+1,Y)+p(X,Y),2)*255',format=monob"\
        -f rawvideo $ofile

    xxd -b $ofile >> output.log
done

And here is output.log:

00000000: 00000000 00000000 00000000 00000000 00000001 00000000  ......
00000000: 00000000 00000000 00000000 00000000 00000011 00000000  ......
00000000: 00000000 00000000 00000000 00000000 00000111 00000000  ......
00000000: 00000000 00000000 00000000 00000000 00001101 00000000  ......
00000000: 00000000 00000000 00000000 00000000 00011111 00000000  ......
00000000: 00000000 00000000 00000000 00000000 00110001 00000000  ....1.
00000000: 00000000 00000000 00000000 00000000 01110011 00000000  ....s.
00000000: 00000000 00000000 00000000 00000000 11010111 00000000  ......
00000000: 00000000 00000000 00000000 00000001 11111101 00000000  ......
00000000: 00000000 00000000 00000000 00000011 00000111 00000000  ......
00000000: 00000000 00000000 00000000 00000111 00001101 00000000  ......
00000000: 00000000 00000000 00000000 00001101 00011111 00000000  ......
00000000: 00000000 00000000 00000000 00011111 00110001 00000000  ....1.
00000000: 00000000 00000000 00000000 00110001 01110011 00000000  ...1s.
00000000: 00000000 00000000 00000000 01110011 11010111 00000000  ...s..
00000000: 00000000 00000000 00000000 11010110 01111101 00000000  ....}.
00000000: 00000000 00000000 00000001 11111110 11000111 00000000  ......
00000000: 00000000 00000000 00000011 00000011 11001101 00000000  ......
00000000: 00000000 00000000 00000111 00000110 01011111 00000000  ...._.
00000000: 00000000 00000000 00001101 00001110 11110001 00000000  ......
00000000: 00000000 00000000 00011111 00011011 10010011 00000000  ......
00000000: 00000000 00000000 00110001 00111110 10110111 00000000  ..1>..
00000000: 00000000 00000000 01110011 01100011 11111101 00000000  ..sc..
00000000: 00000000 00000000 11010111 11100110 00000111 00000000  ......
00000000: 00000000 00000001 11111100 00101110 00001101 00000000  ......
00000000: 00000000 00000011 00000100 01111010 00011111 00000000  ...z..
00000000: 00000000 00000111 00001100 11001110 00110001 00000000  ....1.
00000000: 00000000 00001101 00011101 11011010 01110011 00000000  ....s.
00000000: 00000000 00011111 00110111 01111110 11010111 00000000  ..7~..
00000000: 00000000 00110001 01111101 11000011 11111101 00000000  .1}...

Now I wonder if it’s possible to write a brainf*ck intepreter with FFmpeg.