|
|
|
|
|
|
by quotemstr
20 days 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#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. |
|
|