Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Unicode's transliteration rules are Turing-complete

seriot.ch

Post reply on HN
Print view View original

21–30 of 37 posts

Re: Unicode's transliteration rules are Turing-complete

#21

Post by quotemstr »

From a computer science POV, it's spooky how Turing-completeness arises spontaneously out of the most mundane data-processing machines. You look at UTS#35, see "Transforms provide a set of rules for transforming text via a specialized set of context-sensitive matching rules." and think, "Ah! Rewrite rules! Those are often Turing-complete! Maybe this one is too!".

And so it is (https://en.wikipedia.org/wiki/Semi-Thue_system#Undecidabilit...).

It's a scary and wonderful part of our world that you can bootstrap so much complexity out of a little iterated self-reference.

My only quibble with the article is in this line...

> The surprise is that it lives in a data format for locale files, shipped in every OS, whose specification doesn't mention the possibility.

... I'm not surprised. After all, the processor that interprets the data format is Turing-complete not only in its instructions, but in the page table! See https://github.com/jbangert/trapcc

If anything, when you build a system and it starts to get complex, you have to go out of your way to ensure it's decidable and can't accidentally bootstrap the universe.

Re: Unicode's transliteration rules are Turing-complete

#22

Post by omoikane »

hyperhello wrote: post #12

Does this mean I could post some untransliterated text here in a comment and make your browsers all do these computations?

I don't think most browsers enable transliteration out of the box.

Lynx does[1], but it does that using iconv, which I think doesn't use UTS #35 transliteration rules.

[1] https://lynx.invisible-island.net/lynx2.9.3/CHANGES.html#:~:...

Re: Unicode's transliteration rules are Turing-complete

#23

Post by poizan42 »

kccqzy wrote: post #10
dvt wrote: post #9

Who implements transliteration rules? I assume operating systems? Or text renderers?

The ICU library. It’s so ubiquitous that it’s somewhat difficult to avoid this library if you are doing anything advanced with human text.

Windows has its own library built-in: NLS. There have been a lot of back-and-forth about whether to use NLS or ICU in dotnet on Windows because it resulted in different behavior between Windows and other platforms. I think they ended up using ICU by default from .NET 5 on.

Re: Unicode's transliteration rules are Turing-complete

#25

Post by psidebot »

With 7200 languages in the world, Unicode has to handle things like bidirectional text, contextual shaping, ligatures, character reordering, and stacked characters. Organizations like SIL Global regularly submit whole new scripts. With those sorts of flexibility requirements, it would be more surprising if Unicode lacked Turing complete formatting options.

Re: Unicode's transliteration rules are Turing-complete

#27

Post by beefburger »

ks2048 wrote: post #11

Does the Latin-Katakana example given imply that some input value can cause it to not terminate?

No, standard transliterators like Latin-Katakana are designed to always terminate. What the article demonstrates is that the underlying rule language is powerful enough that one could write custom rules that loop infinitely.

In practice, the ICU implementation does limit the number of rewrites, even though the specification doesn't.

Re: Unicode's transliteration rules are Turing-complete

#28

Post by pwdisswordfishq »

ars wrote: post #19
hyperhello wrote: post #12

Does this mean I could post some untransliterated text here in a comment and make your browsers all do these computations?

Perhaps I've misunderstood, but I think it's not the text that is unicode complete, it's the transliteration rules that are. Unless you install special rules you won't be doing extra computation.

Not even any built-in transliteration rules, but the transliteration rules engine. One has to load a custom ruleset to exploit it – and I presume no sane implementation is going to accept rules from untrusted input.
Post reply on HN