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.) 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.

Contents

Illustration

This is a crop of my JPEG XL implementation of Rule 110. Click it to see the full image.

The first 256 steps of Rule 110 in JPEG XL

Code

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

Is Rule 110 enough?

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 art

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.

Security

JPEG XL’s programmability is not a security risk if implemented as specified. According to a Hacker News 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).

See also


Tags: file format, graphics, my work, programming.