Proving the Turing Completeness of Fonts • Hacker News Board

Re: Proving the Turing Completeness of Fonts

#11

Post by peter_d_sherman » Tue, Mar 12, 2019, 12:42 AM UTC

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.

Re: Proving the Turing Completeness of Fonts

#12

Post by ericsoderstrom » Tue, Mar 12, 2019, 1:17 AM UTC

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

Re: Proving the Turing Completeness of Fonts

#13

Post by zwkrt » Tue, Mar 12, 2019, 2:57 AM UTC

ericsoderstrom wrote: post #12

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

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

Re: Proving the Turing Completeness of Fonts

#14

Post by benj111 » Tue, Mar 12, 2019, 7:03 AM UTC

pcwalton wrote: post #6

benj111 wrote: post #3

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?

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.

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

Re: Proving the Turing Completeness of Fonts

#15

Post by kccqzy » Thu, Mar 14, 2019, 2:57 AM UTC

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.