thaliaarchi
OpenType is not Turing Complete
I present the following sylogism to justify that an OpenType Engine however theoretical, is not Turing Complete. I would be very happy to be proven wrong.
An OpenType engine can only loop infinitely by growing the tape infinitely. A Turing machine can loop infinitely with a finite tape. An OpenType engine is therefore NOT Turing Complete.
Thanks for the note.
My list is meant more as a collection of bizarre things people have done with systems that are assumed to not be very capable, than a definitive proof of each system's Turing completeness. You'll notice many of the demos don't even require the computational power of a Turing machine. For example, the entry for OpenType implements addition. I should be more precise about this, but this is how it currently is.
Since I'm not familiar with the workings of OpenType myself, I lean on what other people have written. If you've got something demonstrating this, I'll gladly link it.
An OpenType engine can only loop infinitely by growing the tape infinitely.
[Citation Needed]
My proof that OpenType shaping is Turing Complete, albeit with a caveat: the machine never halts:
https://www.youtube.com/watch?v=lK_myoawb0U
I mean, looping infinitely is the easiest thing in OpenType: just a Contextual lookup that loops back to itself. No tape needed more than one entry.
Also, for AAT morx fonts I think I also once proved that they are Turing Complete, despite looking like DFAs. It's because of the epsilon-transitions IIRC.