Introduction
When you think of Unicode, the first thing that comes to mind is likely a simple set of symbols representing characters from various languages. However, the truth is that Unicode's transliteration rules are far more powerful than they appear. These rules, as described in document UTS #35, go beyond converting "é" to "e"; they are actually Turing-complete, meaning they can simulate any computation performed by a computer.
An Overview of Transliteration Rules
Transliteration rules work through ordered text rewrites. For example, a rule might stipulate that the sequence "x" should be replaced with "y". More complexly, these rules can include contexts, capture groups, and quantifiers, allowing them to behave conditionally based on the text's environment.
Consider the following example: ``python from icu import Transliterator as T t = T.createFromRules("", "x > y|z; za > w;") print(t.transliterate("xa")) # Output: yw `` In this example, "xa" is transformed into "yw" through a series of rewrites and cursor repositioning, illustrating the complexity and power of these rules.
Turing-Completeness and Tag Systems
To prove the Turing-completeness of Unicode's transliteration rules, they can be compiled into two-tag systems, a model of universal computation. A two-tag system operates by removing the first two letters of a sequence and appending a production based on the first letter.
Take the example of the Collatz function expressed in terms of two-tag systems:
- a → bc
- b → a
- c → aaa
These rules can be translated into Unicode transliteration rules, thus enabling a complete simulation of complex computation.
Practical Example: The Collatz Function
Applying these rules to a mathematical problem like the Collatz function demonstrates the power of this system. This function, which divides an even number by two or applies a formula to an odd number, can be simulated by transliteration using well-defined rules.
Here is how it works:
- Start by marking the beginning of the string with a read marker "M".
- Then apply a series of rules that manipulate the string based on the current character's value.
These rules illustrate how a complex mathematical problem can be translated into text manipulations, highlighting the Turing-completeness of transliteration rules.
Conclusion
The discovery of the Turing-completeness of Unicode's transliteration rules opens up fascinating prospects regarding the capabilities of this system. Beyond simple character conversion, these rules can simulate complex algorithms and perform universal computations.
Let's discuss your project in 15 minutes.