11 ms·

Unicode's transliteration rules are Turing-complete

131 points by beefburger 2mo ago

beefburger 2mo ago
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.
- bielok 2mo ago
  [flagged]
amelius 2mo ago
Nice, but Unicode's codepoint set is far from complete.
dvt 2mo ago
Who implements transliteration rules? I assume operating systems? Or text renderers?
- kccqzy 2mo ago
  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.
  - ks2048 2mo ago
    And ICU uses data from CLDR, which is mentioned in the blog. Here, there are 380 xml files: https://github.com/unicode-org/cldr/tree/main/common/transforms https://github.com/unicode-org/cldr/tree/main/common/transfo... Yes, ICU is ubiquitous. But, some NLP projects use various other libraries, such as uroman (just for romanization - to Latin script).
  - poizan42 2mo ago
    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.
linzhangrun 2mo ago
Waiting for someone to vibe a compiler targeting Unicode transliteration rules...
est 2mo ago
Does it work on modern OS or just PyICU ?
NooneAtAll3 2mo ago
reminds me of Word's autocorrect being turing-complete https://www.youtube.com/watch?v=jlX_pThh7z8 https://www.youtube.com/watch?v=jlX_pThh7z8 (3:57, but whole video is fun)
- deleted 2mo ago
  [deleted]
anankaie 2mo ago
At this point it feels more difficult to ensure that your format cannot compute than to ensure it can
deleted 2mo ago
[deleted]
ks2048 2mo ago
Does the Latin-Katakana example given imply that some input value can cause it to not terminate?
- beefburger 2mo ago
  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.
hyperhello 2mo ago
Does this mean I could post some untransliterated text here in a comment and make your browsers all do these computations?
- ks2048 2mo ago
  I could be wrong, but I don't think it's common for websites to just transliterate any text they're given. Let's check: ウィキペディア
- ars 2mo ago
  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.
  - pwdisswordfishq 2mo ago
    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.
- omoikane 2mo ago
  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#:~:text=additional%20encodings%3A%0A%20%20%2B%20if%20%22-,TRANSLIT,-%22%20feature%20(an%20extension https://lynx.invisible-island.net/lynx2.9.3/CHANGES.html#:~:...
sgjohnson 2mo ago
reminded me of the PowerPoint Turing Machine https://www.youtube.com/watch?v=uNjxe8ShM-8 https://www.youtube.com/watch?v=uNjxe8ShM-8
i18nagentai 2mo ago
[flagged]
- f33d5173 2mo ago
  Your AI has totally misunderstood what's going on here and is really contributing nothing to the discussion.
- techbrovanguard 2mo ago
  shut up, clanker. nobody asked.
SonOfLilit 2mo ago
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).
- edelbitter 2mo ago
  > 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! recent example: https://github.com/python/cpython/issues/149079 https://github.com/python/cpython/issues/149079
- baq 2mo ago
  > 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
- u1hcw9nx 2mo ago
  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.
cyberax 2mo ago
So... Who's porting Doom to run on this?
quotemstr 2mo ago
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#Undecidability_of_the_word_problem 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 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.
- anthk 2mo ago
  https://wiki.xxiivv.com/site/modal https://wiki.xxiivv.com/site/modal
slipperybeluga 2mo ago
[dead]
psidebot 2mo ago
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.
dalf 2mo ago
At another layer : Llama.ttf: A font which is also an LLM https://fuglede.github.io/llama.ttf/ https://fuglede.github.io/llama.ttf/ https://news.ycombinator.com/item?id=40766791 https://news.ycombinator.com/item?id=40766791 (June 23, 2024)
flenserboy 2mo ago
A Turing-complete system open to LLMs will be a security hole.
OrangeMusic 2mo ago
See also: https://beza1e1.tuxen.de/articles/accidentally_turing_complete.html https://beza1e1.tuxen.de/articles/accidentally_turing_comple...

131 points by beefburger 2mo ago

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.

bielok 2mo ago
[flagged]

amelius 2mo ago

Nice, but Unicode's codepoint set is far from complete.

dvt 2mo ago

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

kccqzy 2mo ago
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.
- ks2048 2mo ago
  And ICU uses data from CLDR, which is mentioned in the blog. Here, there are 380 xml files: https://github.com/unicode-org/cldr/tree/main/common/transforms https://github.com/unicode-org/cldr/tree/main/common/transfo... Yes, ICU is ubiquitous. But, some NLP projects use various other libraries, such as uroman (just for romanization - to Latin script).
- poizan42 2mo ago
  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.

linzhangrun 2mo ago

Waiting for someone to vibe a compiler targeting Unicode transliteration rules...

est 2mo ago

Does it work on modern OS or just PyICU ?

NooneAtAll3 2mo ago

reminds me of Word's autocorrect being turing-complete https://www.youtube.com/watch?v=jlX_pThh7z8 https://www.youtube.com/watch?v=jlX_pThh7z8 (3:57, but whole video is fun)

deleted 2mo ago
[deleted]

anankaie 2mo ago

At this point it feels more difficult to ensure that your format cannot compute than to ensure it can

deleted 2mo ago

[deleted]

ks2048 2mo ago

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

beefburger 2mo ago
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.

hyperhello 2mo ago

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

ks2048 2mo ago
I could be wrong, but I don't think it's common for websites to just transliterate any text they're given. Let's check: ウィキペディア
ars 2mo ago
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.
- pwdisswordfishq 2mo ago
  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.
omoikane 2mo ago
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#:~:text=additional%20encodings%3A%0A%20%20%2B%20if%20%22-,TRANSLIT,-%22%20feature%20(an%20extension https://lynx.invisible-island.net/lynx2.9.3/CHANGES.html#:~:...

sgjohnson 2mo ago

reminded me of the PowerPoint Turing Machine https://www.youtube.com/watch?v=uNjxe8ShM-8 https://www.youtube.com/watch?v=uNjxe8ShM-8

i18nagentai 2mo ago

[flagged]

f33d5173 2mo ago
Your AI has totally misunderstood what's going on here and is really contributing nothing to the discussion.
techbrovanguard 2mo ago
shut up, clanker. nobody asked.

SonOfLilit 2mo ago

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

edelbitter 2mo ago
> 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! recent example: https://github.com/python/cpython/issues/149079 https://github.com/python/cpython/issues/149079
baq 2mo ago
> 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
u1hcw9nx 2mo ago
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.

cyberax 2mo ago

So... Who's porting Doom to run on this?

quotemstr 2mo ago

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

anthk 2mo ago
https://wiki.xxiivv.com/site/modal https://wiki.xxiivv.com/site/modal

slipperybeluga 2mo ago

[dead]

psidebot 2mo ago

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.

dalf 2mo ago

At another layer : Llama.ttf: A font which is also an LLM https://fuglede.github.io/llama.ttf/ https://fuglede.github.io/llama.ttf/ https://news.ycombinator.com/item?id=40766791 https://news.ycombinator.com/item?id=40766791 (June 23, 2024)

flenserboy 2mo ago

A Turing-complete system open to LLMs will be a security hole.

OrangeMusic 2mo ago

See also: https://beza1e1.tuxen.de/articles/accidentally_turing_complete.html https://beza1e1.tuxen.de/articles/accidentally_turing_comple...