Live data from Hacker News

Unicode's transliteration rules are Turing-complete

seriot.ch

31–37 of 37 posts

Re: Unicode's transliteration rules are Turing-complete

#31

This is not interesting in the way that "DNS parsing is turing complete" is interesting. Nobody can send you a unicode file and make you run an infinite loop or whatever. Within Unicode is defined a DSL used internally by the library implementers to define some business logic, like most DSLs it is turing complete. Anyone with the ability to make you run their rules file already has the ability to make you run arbitra…

> The person who specified this most likely was aware that this is turing complete and it's the rules author's responsibility not to write infinite loops

Software developer’s job description: prove that this instance of the halting problem you’re being paid to work on today is decidable

Re: Unicode's transliteration rules are Turing-complete

#33

This is not interesting in the way that "DNS parsing is turing complete" is interesting. Nobody can send you a unicode file and make you run an infinite loop or whatever. Within Unicode is defined a DSL used internally by the library implementers to define some business logic, like most DSLs it is turing complete. Anyone with the ability to make you run their rules file already has the ability to make you run arbitra…

ICU's core rule-based transliterator engine based implementations have 16 rewrite limit per input code point. This covers basically all widely used systems in use.

Injecting new rule is into Uinicode transliterator is remote possiblility, but even if that happens, it does very little.

Re: Unicode's transliteration rules are Turing-complete

#35

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…

https://wiki.xxiivv.com/site/modal
Post reply on HN