- Solo con
find y mkdir de GNU también se pueden crear bucles y transiciones de estado aprovechando la creación de directorios y el orden de recorrido, por lo que una combinación de utilidades de archivos se convierte en un modelo de computación
- La demostración se realiza mediante la implementación de un sistema de etiquetas (tag system), y la primera prueba basada en Rule 110 fue corregida por un problema al manejar repeticiones infinitas
- El bucle básico tiene la forma
find x -execdir mkdir x/x \;, donde sigue descubriendo nuevos directorios, y al agregar -regex también permite ramificaciones condicionales como FizzBuzz
- La implementación del sistema de etiquetas representa el estado como una ruta de archivo y copia el resto tras eliminar los primeros
m caracteres mediante referencias inversas (back-reference)
- Como POSIX deja como unspecified el comportamiento cuando se agregan archivos a un directorio mientras se está recorriendo, la conclusión depende del comportamiento observado en herramientas GNU y del entorno presentado
Construir un modelo de computación con GNU find y mkdir
- El objetivo es mostrar que un sistema con solo los comandos
find y mkdir de GNU es Turing completo
- La prueba se desarrolla implementando un sistema de etiquetas
- El flujo completo sigue el orden: construcción del bucle, FizzBuzz e implementación del sistema de etiquetas
- El error de la primera versión de la prueba basada en Rule 110, publicada el 2 de agosto de 2024, fue corregido, y la versión actual fue cambiada a una implementación de sistema de etiquetas
- La primera versión tenía el problema de no poder manejar una cantidad infinita de iteraciones
- El artículo relacionado, Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation, fue aceptado en FUN with Algorithms 2026
El bucle que crea la generación de directorios
- El siguiente código crea directorios de forma recursiva y entra en un bucle infinito
mkdir x
find x -execdir mkdir x/x \;
find x enumera los archivos bajo x, e incluye también a x mismo- Cuando se enumera
x, mkdir crea x/x, y en la siguiente iteración de find se incluye el nuevo x/x
- A medida que este proceso se repite, se siguen creando rutas como
x/x/x y x/x/x/x
- Si se usa la opción
-maxdepth, se puede limitar la profundidad de generación
mkdir x
find x -maxdepth 3 -execdir mkdir x/x \;
- Este ejemplo termina después de crear
x/x/x/x/x
FizzBuzz implementado con find -regex
- La opción
-regex de find permite filtrar los nombres de archivo que serán objetivo de las acciones posteriores
- Al combinar este filtro con el bucle, se implementa un FizzBuzz que determina si la cantidad de
x/ es múltiplo de 3, 5 o 15
- Para facilitar la lectura, el ejemplo usa
-regextype posix-extended, pero se considera que el mismo método también puede aplicarse con otras sintaxis de expresiones regulares
mkdir -p d/x
find d/x -regextype posix-extended -regex 'd(/x){0,29}' -execdir mkdir x/x \;
find d -regextype posix-extended \
-regex 'd((/x){15})+' -printf "FizzBuzz\n" -o \
-regex 'd((/x){5})+' -printf "Buzz\n" -o \
-regex 'd((/x){3})+' -printf "Fizz\n" -o \
-regex 'd(/x)+' -printf "%d\n"
- La segunda línea genera, bajo
d, una ruta en la que x se repite 30 veces seguidas
- La tercera línea imprime
FizzBuzz si la cantidad de x es múltiplo de 15, Buzz si es múltiplo de 5, Fizz si es múltiplo de 3, y en los demás casos muestra la profundidad desde d
- El resultado de ejecución puede verse en este ejemplo de OneCompiler
Mostrar la completitud de Turing con un sistema de etiquetas
- Un sistema de etiquetas se compone de
(m, A, P)
m es un entero positivoA es un alfabeto finito que incluye el símbolo de parada HP son las reglas de producción para cada símbolo del alfabeto
- Dada una cadena inicial, el sistema repite el siguiente proceso
- Si la longitud de la cadena es menor que
m o si el primer carácter es H, se detiene
- En caso contrario, agrega
P(x) al final de la cadena para el primer carácter x
- Elimina los primeros
m caracteres
- Se sabe que un sistema de etiquetas con
m=2 y |A|=576 es una máquina de Turing universal, y cualquier sistema capaz de ejecutar un sistema de etiquetas de ese tamaño es Turing completo
- Como ejemplo de implementación real, se usa el simple sistema 2-tag de Wikipedia con
m=2 y |A|=4
La forma de usar rutas de archivo como estado
- La idea central es seguir concatenando el siguiente estado al final de una ruta de archivo que representa el estado actual
- Se usa
_ como separador entre estados
- Ejemplo:
_/b/a/a/_
- Si el siguiente estado es
a/c/c/a, la ruta pasa a ser _/b/a/a/_/a/c/c/a/_
- Está diseñado para que durante la ejecución no haya más de un archivo dentro de un mismo directorio
- La implementación sigue agregando el siguiente estado hasta encontrar el símbolo de parada o hasta que la longitud de la cadena sea menor o igual que
m
- La expresión condicional de
find opera en tres partes principales
- Verificación de la condición de parada
- Uso de referencias inversas para copiar, desde el estado anterior, el resto tras eliminar los primeros
M caracteres
- Aplicación de las reglas de producción para
a, b y c
- Las reglas de producción de ejemplo son las siguientes
M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"
- Como resultado de la ejecución, se imprime el valor esperado
_/H/c/c/c/c/c/c/a/_
- Ese resultado también se ofrece en este ejemplo de OneCompiler
Referencias inversas y posibilidades de expansión
- La implementación de FizzBuzz usa expresiones regulares normales, pero la del sistema de etiquetas utiliza la referencia inversa
\2
- Gracias a la referencia inversa, se puede copiar desde el estado anterior la parte que queda después de excluir los primeros
m caracteres
- Esta construcción puede ampliarse a alfabetos de tamaño constante más grande
- Si faltan caracteres disponibles, se puede resolver usando más de un carácter por nombre de archivo
- Por lo tanto, se llega a la conclusión de que la combinación
find + mkdir es Turing completa
Restricciones de POSIX y entorno de ejecución
- Debido a los límites de longitud de las rutas, podría no ser posible ejecutar autómatas de tamaño arbitrario, pero el código presentado está construido para no pasar directamente a
mkdir rutas de longitud arbitraria
- En las pruebas,
find funcionó incluso con rutas de más de 30000 caracteres, y no se encontró un límite aparte
- No hay garantía en la especificación de POSIX
- La documentación de POSIX para
find especifica que el comportamiento es unspecified cuando se agregan archivos al directorio que se está recorriendo
- No se verificó el comportamiento de herramientas distintas de GNU
- El entorno usado fue el siguiente
find (GNU findutils) 4.8.0
mkdir (GNU coreutils) 8.32
Linux DESKTOP-5JU1LI7 5.15.153.1-microsoft-standard-WSL2 #1 SMP Fri Mar 29 23:14:13 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux
1 comentarios
Comentarios de Hacker News
Ya lo dice arriba de todo en la página: se retiró la afirmación de la completitud de Turing de find + mkdir
Dice que, debido a un defecto en la prueba, se retira la afirmación de haber demostrado que find + mkdir es Turing completo, y que vean https://news.ycombinator.com/item?id=41117141
También dice que actualizarán el artículo si logran corregir la prueba
¿Se puede implementar Folders con esto?
https://www.danieltemkin.com/Esolangs/Folders/
Las entradas de directorio ocupan espacio dentro del MFT, pero Explorer solo cuenta los bloques asignados en otra parte, así que simplemente no lo muestra
Si sigues creando directorios vacíos, el MFT crece y al final sí aparece un problema de espacio
Con archivos pequeños pasa algo parecido: un archivo de texto vacío se ve con tamaño de 0 bytes y tamaño en disco de 0 bytes, y aunque le pongas unos 400 bytes, los datos caben dentro de la entrada de directorio preasignada en el MFT, así que en Explorer sigue apareciendo con tamaño en disco de 0
Si duplicas los datos, se asignan bloques de disco y pasa a verse con longitud de 800 bytes y tamaño en disco de 4,096 bytes; si luego lo vuelves a reducir a 400 bytes, los datos no regresan al MFT, así que sigue ocupando 4,096 bytes
Aun así, eso no impide disfrutar el resultado, que en general está muy bueno
No entiendo cómo esto demuestra la completitud de Turing
La implementación del autómata de la regla 110 parece estar limitada tanto por el ancho como por la cantidad de iteraciones
La cantidad de estados para un ancho dado es finita, así que no es Turing completo, y como además siempre termina, tampoco lo es
¿Se puede escribir una implementación de regla 110 con ancho y profundidad arbitrarios, es decir, infinitamente ampliables?
Las computadoras reales también usan memoria finita en vez de una cinta infinita, así que no cumplirían esa condición sin importar el lenguaje o el método
También dice que actualizará el artículo si logra corregir la prueba
Retirado
Dice: “debido a un defecto en la prueba, retiro la afirmación de haber demostrado que find + mkdir es Turing completo”
Pensé que iba a usar una forma interesante de cálculo lambda, pero en realidad solo dependía del parser de expresiones regulares de find para hacer los cálculos
Un ejemplo memorable es http://realgl.blogspot.com/2013/08/battlecode.html; vean la parte de “Regular Expression Pathfinding”
Parece que esta prueba sería mucho más simple si usara un sistema de etiquetas en lugar de un autómata celular (https://en.m.wikipedia.org/wiki/Tag_system)
Ninguna implementación puede ser infinita, pero en este caso el PATH_MAX, que normalmente vale 4096, parece especialmente bajo
En GNU parece funcionar incluso con longitudes de ruta mayores a 4096
Aparentemente lo probaron con longitudes de ruta de hasta 30k
El software o los servicios que implementan o consumen expresiones regulares (RE, RegExp), o los componentes dentro de una cadena de software/servicios, pueden ser potencialmente Turing completos
En ese contexto, si la seguridad es importante, habría que auditar si hay completitud de Turing o no
Para obtener completitud de Turing hacen falta 2 pilas
Pero muchas bibliotecas de expresiones regulares soportan muchísimo más que una simple “expresión regular”
Mi find no solo es demostrablemente Turing completo, sino que además no es una Turing tarpit y compila a código nativo