The NSO hack wasn't "running a Turing machine inside a GIF file", it was not a Turing machine nor was there an actual GIF file involved. The actual story is even more amazing/scary than that though. They used bitwise operations like OR and NOT made possible via an obsolete part of the PDF standard to emulate NAND gates - then using 70K of those implemented a simple 64 bit CPU to search RAM allowing them to bypass ASLR defenses! One can only guess the number of man hours from VERY smart people that went into developing it. I've linked the Project Zero writeup below but it kind of elides a few details so I'll post a simplified account here.
The first stage of the exploit is of the type we're all too familiar with. In this case there was a bug in iMessage where a method that was intended to copy a GIF upon receipt did so by rendering it into a new GIF - and that rendering occurred outside of Apple's "BlastDoor" sandbox. Worse, any file ending in ".gif" was passed to this method, but the image renderer detected the type of image so it worked on any image type. Thus in this exploit, a PDF was provided with a GIF extension, which caused that to be rendered.
The second stage of the exploit leveraged a bug in open source JBIG2 code used inside Apple's PDF decoder which allowed a buffer overflow to access arbitrary memory. Perfect example of "legacy debt" since JBIG2 is functionally obsolete, but some very old PDF files won't render without it.
Since there was no way to run any code at this stage the worst that could be done with this exploit would be to crash the phone - since the use of ASLR means you don't know what is where without the ability to search through memory for something specific.
In the third stage they solved the inability to run code by leveraging JBIG2's bitmap operations to emulate AND, OR, XOR and XNOR, which of course allows emulating NAND gates. They used 70,000(!) such operations to emulate a simple 64 bit CPU, which allowed searching through memory to find what they needed, and move onto the fourth and subsequent stages of the exploit which eventually leveled up enough to take complete control of the phone. Who knows how many separate exploits were ultimately strung together to achieve that, and how much work went into them all (though some may have been purchased from others rather than developed in house)
Project Zero writeup