Birbla

Discussion summary

Discussions highlight that Unicode's transliteration rules are Turing-complete, with implementations mainly via ICU library. The concept raises questions about practical applications and browser support.

What the discussion says

  • ICU library is central to implementing transliteration rules.
  • Most browsers do not support Unicode transliteration natively.
  • Transliteration rules can lead to complex computations, but are not commonly used in websites.
  • Some tools like Lynx use different methods for transliteration.
“It's spooky how Turing-completeness arises from mundane data-processing machines.”
— quotemstr
“Most browsers don't enable transliteration out of the box.”
— omoikane

Join the discussion

Write your take first — we'll ask for email only when you're ready to publish.

Sign in
  • Hacker News
  • Does the Latin-Katakana example given imply that some input value can cause it to not terminate?
    by ks2048
  • 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.
    by psidebot
  • 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.

    by quotemstr
  • reminds me of Word's autocorrect being turing-complete https://www.youtube.com/watch?v=jlX_pThh7z8 (3:57, but whole video is fun)
    by NooneAtAll3
  • At this point it feels more difficult to ensure that your format cannot compute than to ensure it can
    by anankaie
  • 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.
    by beefburger
  • 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).

    by SonOfLilit

Explore Birbla archives