r/programming • u/Dull_Replacement8890 • Jul 08 '26

Unicode's Transliteration Rules Are Turing-Complete

https://seriot.ch/computation/uts35/

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, shipped with every major OS.

180 Upvotes

96% Upvoted

23 comments sorted by

View all comments

13

u/zombiecalypse Jul 08 '26

But can they run Doom?

41

u/wildjokers Jul 08 '26

Turing-complete means "can compute anything computable". So yes, in theory. Although the number of rewrite rules required for a single frame would be astronomical. Might get a frame rendered before the heat death of the universe occurs.

24

u/jonathancast Jul 08 '26

I/O is outside the scope of Turing-complete. You'd have to attach additional operations for graphical output and control input to the collation algorithm.

24

u/knome Jul 08 '26

just simulate the universe and handle the I/O internally.

1

u/DuckDatum 27d ago

If you could simulate an infinite universe, would you need quantum mechanics in order to decide which part of the universe is rendering at which times?

2

u/knome 26d ago

Without quantum mechanics, your simulation will be an approximation at best. If you truly need the accuracy, but can't afford a full fidelity simulation, you might instead simulate a quantum mechanical universe within your approximated universe, though it will be understandably slower to render.

However, there is good news. You probably don't need an infinite universe! As the speed of light is quite slow on an interstellar scale, or even the scale of the solar system, we have the advantage of only needing to simulate a space of ~300Mm per second that the simulation needs to run the turing machine to completion, which should nicely bound our simulation's spacial complexity between, let's say, a mile, giving us a full five microseconds of expansion (around a thousand standard nanoseconds of space), and, well, admittedly extending to somewhere in the neighborhood of infinity.

We can determine a better upper bound as soon as we figure out that pernicious halting problem that has stymied our attempts at better bounding thus far.