JPEG XL would be Turing-complete

The JPEG XL image format includes so-called “predictors”, small programs that improve compression by expressing the color of a pixel in terms of the colors of its neighbors. It is possible to implement the Rule 110 cellular automaton in JPEG XL predictors. (It wasn’t anything complicated, but I think I was the first to do it. I originally posted the code on the pouët.net BBS.) Since Rule 110 is Turing-complete, this seems to prove that JPEG XL predictors are themselves Turing-complete—except they are not! To enable parallel encoding and decoding, the JPEG XL codec works on slices of images up to 1024 by 1024 pixels in size called “groups”. So JPEG XL itself isn’t Turing-complete; a version of it without the 1024×1024 pixel limitation would be.

This is a crop of my JPEG XL implementation of Rule 110. Follow the link for the full image.

The first 256 steps of Rule 110 in JPEG XL.

When I wrote the code below, the source code format for JXL predictors didn’t have comments or constants, which I wanted to make it easier to understand. This is why the code needs a preprocessing step. Before you compile it, apply the sed command sed 's|\s*;.*$||;s|t 1|t 255|;s|-1|-255|' to strip out the comments and convert ±1 to ±255.

You can load and run the already preprocessed code in the JXL Art playground.

if y > 0
  if N > 0
    if NW-N > -1   ; N  = 1
      if N-NE > 0  ; NW = 1
        - Set 1    ; NE = 0
        - Set 0    ; NE = 1
      - Set 1      ; NW = 1, NE = 0/1
    if NW-N > 0    ; N  = 0
      if N-NE > -1 ; NW = 1
        - Set 0    ; NE = 0
        - Set 1    ; NE = 1
      if N-NE > -1 ; NW = 0
        - Set 0    ; NE = 0
        - Set 1    ; NE = 1
  if x > 1022
    - Set 255
    - Set 0

Reddit commenter ConcernedInScythe notes:

Implementing Rule 110 alone doesn’t really demonstrate ‘Turing completeness’, as the universal Turing machine construction used to prove that required a specific setup that included a spacially and temporally periodic background pattern filling the entire universe. You need to be able to convincingly emulate that on an unbounded scale to prove Turing completeness via Rule 110.

A finite version of this seems quite possible to do in JPEG XL without 1024×1024 groups. We can generate any initial state with conditionals on x for y = 0 (one conditional fewer than there are unbroken sequences of zeros and ones). We emulate the infinitely repeating series of production rules and clock pulses constructed by Matthew Cook with series that are long enough for the computation we intend to carry out. We start with some fixed image dimensions, generate the series, and run the computation. If the tag system doesn’t halt, we double the size of the image and try again until it halts or we run out of memory. This comes as close to Turing-completeness as other virtual machines on a physical computer. (If this is wrong, corrections are welcome!)

JPEG XL predictors are used to create art. You can see some of it in the JXL Art Gallery of JPEG XL developer Jon Sneyers, who pioneered predictor art, and on the #jxl-art channel in the JPEG XL Discord. The Gallery requires a browser that supports JPEG XL.

JPEG XL’s programmability is not a security risk if implemented as specified. According to a comment by Jon Sneyers,

It’s not a security risk though: the decode computation per pixel is still bounded, so there is no way to make the decoder go into an infinite loop or anything like that. In that respect it’s (intentionally) not Turing complete, unlike some other image formats like PostScript and SVG that do have actual programming languages in them that can cause a decoder/interpreter to go into an infinite loop (safe handling of such files does require sandboxing and time-outs).