logoalt Hacker News

quotemstrtoday at 4:27 AM0 repliesview on HN

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.