La completitud de Turing de `find` y `mkdir`

Resumen

• Un intento de demostrar que el sistema es Turing completo usando solo los comandos find y mkdir de GNU
• Aunque la completitud de Turing de sed y awk es bien conocida, no hay referencias sobre la completitud de Turing de find y mkdir
• La demostración utiliza una técnica general que muestra que se puede ejecutar Rule 110
• Se explica en el orden de implementación de bucles, FizzBuzz y Rule 110

Implementación

Construcción de un bucle

• El siguiente código crea directorios de forma recursiva y genera un bucle infinito

  mkdir x
  find x -execdir mkdir x/x \;
  

• find x enumera los archivos debajo de x, y cuando x aparece en la lista, crea x/x
• Para limitar la profundidad de creación de directorios, se usa la opción -maxdepth

  mkdir x
  find x -maxdepth 3 -execdir mkdir x/x \;
  

FizzBuzz

• Usando la opción -regex de find para filtrar nombres de archivo y combinándola con el bucle, se implementa FizzBuzz

  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"
  

Implementación de Rule 110

• Una vez que se pueden usar bucles y bifurcación condicional, es posible escribir programas arbitrarios
• Esto se demuestra implementando Rule 110

  WIDTH=16
  ITER=15
  mkdir -p p/0/0/0/0/0/0/0/0/0/0/0/0/0/0/0/1
  O='(/?1)'
  Z='(/?[0p])'
  X='(/?[01p])'
  W0="($X{$WIDTH})"
  W1="($X$W0)"
  W2="($X$W1)"
  ZERO="($Z$Z$Z|$O$Z$Z|$O$O$O)"
  ONE="($O$O$Z|$O$Z$O|$Z$O$O|$Z$O$Z|$Z$Z$O)"
  find p -regextype posix-extended \
  -regex "$W1$W2{$ITER}" -fprint /dev/null \
  -o -regex "$W1$W2{0,$ITER}" \( -execdir mkdir 0/p 1/p \; -o -execdir mkdir 0/p/p 1/p/p \; \) \
  -o -regex "$W2*" -fprint /dev/null \
  -o -regex "$X*$ZERO$W0" -execdir mkdir 0/0 1/0 p/0 \; \
  -o -regex "$X*$ONE$W0" -execdir mkdir 0/1 1/1 p/1 \; \
  2> /dev/null
  find p -regextype posix-extended \
  -regex "p$W2{0,$ITER}" -execdir find p -mindepth $WIDTH -maxdepth $WIDTH \;
  

Preguntas y respuestas previstas

• ¿No impide el límite de longitud de las rutas de archivo ejecutar autómatas de tamaño arbitrario?

  • mkdir falla si se le pasa una ruta de archivo de cierta longitud o mayor, pero el código anterior evita ese problema
  • find funciona incluso con rutas superiores a 30000

• ¿Se garantiza que el código anterior funcione según la especificación POSIX?

  • No; si se agregan archivos durante la búsqueda de directorios, el comportamiento no está especificado
  • Versiones de las herramientas usadas:

    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
    

Resumen de GN⁺

• El intento de demostrar la completitud de Turing usando solo los comandos find y mkdir es interesante
• El enfoque de probarlo mediante una implementación de Rule 110 es creativo
• Aunque no hay garantía de funcionamiento según la especificación POSIX, funciona correctamente con herramientas GNU
• Proyectos con funciones similares incluyen sed y awk