JPEG XL would be Turing-complete

submited by

Style Pass

2021-06-19 12:00:03

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 help with parallel decoding, JPEG XL decoders work on slices of images 1024 by 1024 pixels in size. So JPEG XL itself isn't Turing-complete; a version of it without the 1024×1024 pixel limitation would be.

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.

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.