Proving the Turing Completeness of Fonts

Proving the Turing Completeness of Fonts(litherum.blogspot.com)

61 points by pixelambacht 7 years ago | 14 comments

mLuby 7 years ago |

>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 7 years ago | |

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

benj111 7 years ago |

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 7 years ago | |

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.

benj111 7 years ago | | |

Thanks

So from what I understand these would be called from the UI libraries eg GTK in Linux land. I would assume window managers also, to deal with title bars.

I would further take from this that we shouldn't expect full Unicode support in virtual terminals (not emulators) in the future.....

paradroid 7 years ago |

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

XaspR8d 7 years ago | |

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...

yorwba 7 years ago | | |

> Javascript is unable to access information about actual glyphs rendered or other "font-internal" calculations.

Just render the text to a canvas and read out the pixel data to see the glyphs, a.k.a. canvas fingerprinting. I'm not sure whether getting clever with the font would reveal any information you can't get more easily, though.

kccqzy 7 years ago |

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 7 years ago |

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 7 years ago | |

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

peter_d_sherman 7 years ago |

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 7 years ago |

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

0_gravitas 7 years ago |

Any font is turning complete if you use it in powerpoint