Las reglas de transliteración de Unicode son Turing-completas

Unicode's transliteration rules are Turing-complete

Nicolas Seriot demuestra que las reglas de transliteración de UTS #35, utilizadas en la biblioteca ICU de Unicode, pueden simular cualquier máquina de Turing. Al compilar un sistema de 2-tags, muestra que tres reglas bastan para computar la función de Collatz, y que el problema de la detención es indecidible. Aunque ICU limita el número de reescrituras, la especificación no lo hace, lo que convierte los archivos de reglas en programas potencialmente infinitos. Un hallazgo sorprendente sobre un formato de datos aparentemente inofensivo.