Consideremos un sistema de reescritura que use el alfabeto formado por las tres letras siguientes: la letra a, la b y las comillas. Ocuparemos solamente los strings que tengan una cantidad par de comillas. Es decir, tendremos la siguiente regla (implícita, por así decirlo):
Regla 1: Cuando un string tiene una cantidad impar de comillas, se agrega una comilla al final del string.
Tenemos, además, una segunda regla "implícita":
Regla 2: Las letras a al comienzo del string se borran.
Dada la regla 1, tiene sentido hablar de las letras que están "al interior" de las comillas y de las que están "al exterior". El sistema de reescritura funciona iterando eternamente la siguiente regla (principal, por así decirlo):
Regla 3: Al interior de las comillas, las letras a se transforman en comillas, y las b quedan tal cual. Al exterior de las comillas, las b se transforman en comillas y las a quedan tal cual. Finalmente, los pares de comillas propiamente tales se transforman de acuerdo al siguiente sistema: la primera comilla se transforma en a y la segunda en b.
Ejemplo (cualquiera): ab"bb, b"bb", "abbb, "abbb", a"bbbb, "bbbb", abbbbb, bbbbb, """"", """""", ababab, etc.
Conjetura: Este armatoste converge (siempre).
Blog de Pablo Sáez, de temas varios, principalmente matemática+informática.
