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 arbitrary code (it's a software vendor for software you use).
It's still always fun to find Weird Machines, but as they go, this one is not very weird (it's one of the known families of programming languages, the Mathematica language being the most well known example. 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).
> Nobody can send you a unicode file and make you run an infinite loop or whatever.
I find it interesting/weird (that the spec is written in such unrestricted DSL) for pretty much that reason. They could send you input for rules that are in the spec, and hope you translated them to your programming language of choice in a fairly straightforward manner. Which may then have perfectly acceptable average runtime properties, whether you do it in UTF-8 or UTF-32 (fixed-width) space .. but a worst-case that can reliably be triggered with chosen input!
I've been wondering for a while if anything in Unicode could accidentally compute. It turns out that UTS #35 transliteration rules are Turing-complete. I show how to compute Collatz with just 3 rewrite rules running on stock ICU.
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.
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.
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.
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.
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!".
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.
This is a good example of why text infrastructure should not automatically be treated as data plumbing. Transliteration rules look declarative, but once a rule system can keep rewriting its own output, you have to think about termination, resource limits, and adversarial input.
The practical takeaway for me is not "do not use transliteration rules." It is to run them with the same boring guardrails you would put around regexes supplied by someone else: bounded input, bounded output, max passes, timeout, and observability when a rule set hits the limit. Unicode bugs are often framed as correctness problems, but a lot of the production failures are availability problems caused by text that is valid, unusual, and much more expensive than expected.
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 arbitrary code (it's a software vendor for software you use).
It's still always fun to find Weird Machines, but as they go, this one is not very weird (it's one of the known families of programming languages, the Mathematica language being the most well known example. 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).
I find it interesting/weird (that the spec is written in such unrestricted DSL) for pretty much that reason. They could send you input for rules that are in the spec, and hope you translated them to your programming language of choice in a fairly straightforward manner. Which may then have perfectly acceptable average runtime properties, whether you do it in UTF-8 or UTF-32 (fixed-width) space .. but a worst-case that can reliably be triggered with chosen input!
recent example: https://github.com/python/cpython/issues/149079
In practice, the ICU implementation does limit the number of rewrites, even though the specification doesn't.
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#:~:...
Unless you install special rules you won't be doing extra computation.
Yes, ICU is ubiquitous. But, some NLP projects use various other libraries, such as uroman (just for romanization - to Latin script).
https://www.youtube.com/watch?v=uNjxe8ShM-8
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.
The practical takeaway for me is not "do not use transliteration rules." It is to run them with the same boring guardrails you would put around regexes supplied by someone else: bounded input, bounded output, max passes, timeout, and observability when a rule set hits the limit. Unicode bugs are often framed as correctness problems, but a lot of the production failures are availability problems caused by text that is valid, unusual, and much more expensive than expected.