hey, did you know that the compression format DEFLATE can be used to simulate a cellular automaton, or do multiplication, or, theoretically, anything else you want?
a couple years ago, I had an idea for an esolang: a PNG-style image format that would "happen" to involve enough self-reference to be turing-complete. eventually, struggling to come up with a reason for the program to be split between pixel data and compression, I simplified my goal to just a turing-complete compression format, modeled after DEFLATE, the compression used in PNG (as well as in other common formats)
in thinking about this, though, it occurred to me to wonder: what could be done with DEFLATE itself? the main obvious limitation would be that an individual DEFLATE stream gets decoded in one pass, element-by-element, and then is done; it always halts, and there's limited potential for self-reference
so, in order to make computation more viable, I decided to consider an iterative process of decompression, where one DEFLATE stream is decompressed to produce another, which is decompressed again, etc; this process requires some extra behavior outside the compression format itself, but it's a minimal amount (just a basic loop)
in order for this to work, I needed a DEFLATE stream that would endlessly decompress to DEFLATE streams, so my first step was to create a DEFLATE quine -- a stream that specifically decompresses to itself. (the way I accomplished this was more complicated than necessary -- involving carefully-selected code definitions to create specific bit patterns in an otherwise-empty compressed block -- but it worked)
once I had a quine, I just needed to attach some data to it that was allowed to change. to do this, I created Kwert, a language that compiles to DEFLATE and corresponds closely to how the format works -- it has a self-modifying program consisting of "commands" that can copy sequences of previous commands (corresponding to compressed DEFLATE blocks, which work in part by copying previously-output sections of data), and then skip evaluation of some number of following commands (corresponding to uncompressed DEFLATE blocks, which output some amount of following data as-is)
I was able to create a couple interesting things with Kwert (such as a fibonacci program of sorts), but for a while I struggled to come up with a way to do anything more complex; I had a sense that it might be possible to implement a tag system of some kind -- a computational model that can simulate a turing machine using a queue of symbols, something that's well-suited for a language like Kwert that involves start-to-end modification of the program -- but I couldn't think of a way to use commands as data without them being evaluated and producing an unwanted effect
then, a couple weeks ago, I followed up on an idea I had written down previously: that commands could potentially be transferred as data without side-effects by having it so when they're being used as data, they're positioned such that all they do is copy a no-op command
using this strategy, I was able to design a system in which sections of a Kwert program simulate a string of symbols, which change over time based on preceding symbols. I created a new language, Kmid, based on this concept
Kmid, although more like a cellular automaton than a conventional programming language, is definitely easier to do things with than Kwert, and I was finally able to implement Bitwise Cyclic Tag (a simplified but equally powerful version of tag systems) and confirm that it does successfully compile to DEFLATE, which means, to the best of my knowledge, that iterated inflation is indeed turing-complete!
but DEFLATE's computational ability isn't entirely limited to that theoretical result; there are some at least somewhat interesting things that you can actually see it do (as opposed to everything being theoretically possible but not viable to execute in practice) -- you can see some programs I've written, such as the aforementioned multiplication and rule 110 cellular automaton, on github, some accompanied by instructions and/or links to the CyberChef tool to more conveniently run the DEFLATE versions
