Wholly brainfuck

2021-05-15, post № 244

C, brainfuck, #querying

Sparked by a vague idea to query the space of all brainfuck programs — which indeed came to fruition and is detailed in my recent paper Going for a miniKanren implementation. — I thought to capture a miniscule glimpse of said space in a two-dimensional visualization:

All $2^{12+12}$ generalized 𝟨-long brainfuck programs’ initial three bytes of output.

Not wasting precious image real estate, each pixel corresponds spatially to a unique generalized brainfuck program and its color to a property of this program’s execution. In the visualization shown above, this property is defined as the last three bytes written, directly mapped to one byte wide three-channel RGB colorspace.
Trying to find an easily computable as well as fitting program to pixel coordinate mapping, I generalized brainfuck programs defined as finite strings of eight-valued tokens $\mathfrak{B}:=\bigcup_{\ell\geq 0}\mathbb{Z}_8^\ell$ to abrubtly exit when encountering mismatched parentheses whilst executing. As such, the inclusion $(\mathbb{F}_2^3)^\ell\cong\mathbb{Z}_8^\ell\hookrightarrow\mathfrak{B}$ allows for a bit string whose length is divisible by three to be interpreted as a brainfuck program. Furthermore, the brainfuck input token , is interpreted as a no-op since I aim for a pure invocation.
Using a row-major image data representation, each pixel is uniquely associated to a nonnegative index which can be interpreted as a bit string and thus a brainfuck program. Assuring this bit string’s length’s divisibility by three can be done by either filling with zeros or choosing image dimensions adequately.
Source: wholly-brainfuck.c

With its $2^{24}$ pixels each holding three bytes of color entropy, the above image possesses quite a lot of intricacy which gets quickly lost to scaling when attempting to view it in its entirety all at once. To allow for a more local and thus less murky appreciation of the patterns produced, I wrote a concise shell script which takes an approximately uniformly pseudo-randomly chosen rectangular subsection to be set as a wallpaper: wholly-brainfuck_wallpaper.sh, conveniently callable as:

% curl -fsSL https://blog.jfrech.com/244/wholly-brainfuck_wallpaper.sh | sh

Other properties apart from stdout’s bytes are possible — runtime being a one-dimensional one, here shown in a monochromatic look:

All six tokens long brainfuck programs, colored according to their capped runtime.