Por @Alvy — 22 de Febrero de 2022

regex turing machine

Esta curiosidad de 0xdanelia llamada Regex Turing Machine es una demostración de cómo se puede utilizar el Notepad++ como sistema Turing completo utilizando las expresiones regulares y el comando buscar/reemplazar. En la imagen puede verse el código del castor afanoso, uno de los ejemplos por antonomasia. Recordemos que, por definición:

(…) un sistema Turing completo es aquel que tiene un poder computacional equivalente a la máquina de Turing universal. En otras palabras, el sistema y la máquina universal de Turing pueden emularse entre sí.

Esto quiere decir que si el sistema es Turing completo puede emular calculadoras, sistemas operativos, videojuegos o cualquier otro sistema computacional – siempre que se disponga de una capacidad de memoria infinita y un tiempo de ejecución ilimitado, claro. Lo cual no es así en la práctica, pero lo importante como sabemos es el conceto.

La gente ha utilizado tradicionalmente todo tipo de inventos e instrumentos a cual más raruno como sistemas Turing completos: desde Powerpoint, circuitos de canicas, el autómata celular del Juego de la vida, mecanos y lenguajes esotéricos. Sí: con cualquiera de ellos podrías ejecutar Excel, jugar al Doom o realizar cálculos estadísticos.

En la construcción de 0xdanelia para el Notepad++ se utiliza una «cinta» con símbolos en forma de letras (W = escribir, C = nombre de la instrucción, M0 y M1 para los movimientos…) y luego requiere abrir el buscar esta expresión regex:

^!0([01]{20})([01])([01]*\r\n\[ +\^\r\n#)(.*)\r\n(?=(.*\r\n)*^>\4\.\2:([01])((0)|1)(.*\r\n))

y reemplazarla por

!\8\8\1\6\3\9

El meollo del truco está en el poderío de las expresiones regulares, en cuyos grupos (datos entre paréntesis) puede codificarse la información que luego se reemplaza, busca y se repite una y otra vez. El resultado es tan raro como inútil, pero ahí está la gracia del asunto.

(Vía @algoritmic.)

Relacionado:

Compartir en Flipboard Publicar / Tuitear