Proving the Turing Completeness of Fonts

[mLuby]

>But even in HarfBuzz and CoreText, there are hard limits on the recursion depth. HarfBuzz sets its limit to 6. Therefore, the above example will only work on strings of length 7 or fewer. HarfBuzz is open source, though, so I simply used a custom build of HarfBuzz which bumps up this limit to 4 billion. This let me recurse to my heart’s content. A limit of 6 is probably a good thing; I don’t think users generally expect their text engines to be running arbitrary computation during layout.

Truly, Zalgo waits just beyond the wall.

[zamalek]

What we need is a Regex parser written in this language, and I can finally start on my HTML renderer font.

[benj111]

Fonts aren't really something I've dived into.

Could someone explain at what level this is happening. What classes of software/libraries are affected?

[pcwalton]

GSUB handling is done by a library called a text shaper. Examples of libraries that do shaping include the cross-platform HarfBuzz, Windows DirectWrite, and macOS Core Graphics/Core Text.

[paradroid]

Can you use this to bypass Spectre mitigations in Javascript? You would need to measure time, somehow.

[XaspR8d]

It's not arbitrary code execution, just a toy observation about the specification. Additionally, 1) as noted, none of the font rendering libraries used were capable of recursion without the author's modifications, 2) in a web context, Javascript is unable to access information about actual glyphs rendered or other "font-internal" calculations.

If anything, exposing glyph data to the web API would be a bigger problem for fingerprinting, and probably expose some sort of user browsing history snooping flaw...

[kccqzy]

I think this is extremely interesting. Not to dismiss the author's work, but merely performing addition is far from Turing complete. Addition is primitive recursive, a much smaller class of functions than say, generally recursive. Although in this case I have no reason to doubt that GSUB isn't Turing complete, because recursive symbol substitution is powerful enough.

[ericsoderstrom]

Isn't basically every moderately expressive system Turing complete? Even the Magic the Gathering card game is turing complete

https://www.toothycat.net/~hologram/Turing/HowItWorks.html

[zwkrt]

That doesn't make it any less fun to find out /how/ they are Turing complete!

[peter_d_sherman]

Excerpt: "Also, each mapping in the table acts as an “if” statement because it only executes if the pattern is matched."

This can be generalized as: Pattern Matching = if statement.

I don't know nor can I prove that that's true under all circumstances, however...

But, an interesting article.

[empath75]

Seems like lambda calculus would have been a more natural thing to implement since it’s basically just symbol substitution.

[0_gravitas]

Any font is turning complete if you use it in powerpoint