Remix.run Logo
Unicode's transliteration rules are Turing-complete(seriot.ch)
55 points by beefburger 18 hours ago | 15 comments
SonOfLilit 6 minutes ago | parent | next [-]

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

cyberax 2 minutes ago | parent | prev | next [-]

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

beefburger 18 hours ago | parent | prev | next [-]

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 17 hours ago | parent [-]

Huh, very interesting find, and very lean website (:

anankaie 2 hours ago | parent | prev | next [-]

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

ks2048 2 hours ago | parent | prev | next [-]

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

NooneAtAll3 2 hours ago | parent | prev | next [-]

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

hyperhello 2 hours ago | parent | prev | next [-]

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

ks2048 an hour ago | parent [-]

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: ウィキペディア

linzhangrun 2 hours ago | parent | prev | next [-]

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

sgjohnson an hour ago | parent | prev | next [-]

reminded me of the PowerPoint Turing Machine

https://www.youtube.com/watch?v=uNjxe8ShM-8

dvt 2 hours ago | parent | prev | next [-]

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

kccqzy 2 hours ago | parent [-]

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 an hour ago | parent [-]

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

Yes, ICU is ubiquitous. But, some NLP projects use various other libraries, such as uroman (just for romanization - to Latin script).

est 2 hours ago | parent | prev [-]

Does it work on modern OS or just PyICU ?