this wasn't Turing-complete until they exploited it to make it so. JBIG2 executes arbitrary binary bitmap operations, but sequentially (no looping.) using the exploit they presumably found a way to send it into a loop, probably by overwriting the pointer to the next segment or something.

theoretically I guess you don't need that, but you'd have to send a payload linear in size to the number of cycles expected to run the shellcode, and that wouldn't lend itself to a processor-like design - it'd just be too big.

This reminds me of the original story of Mel in which Mel managed to do similar things with assembly. Amazing stuffs and wish I had a chance to work with similar genius.

Basically anything that exceeds the regular category is risky and difficult to secure. See weird machines / langsec. This is a prime example.

Well, when combined with an integer overflow at least.