La complétude de Turing de `find` et `mkdir`

Vue d'ensemble

• Tentative de démontrer qu'un système est Turing-complet en n'utilisant que les commandes GNU find et mkdir
• La complétude de Turing des commandes sed et awk est bien connue, mais il n'existe pas de référence sur celle de find et mkdir
• La démonstration s'appuie sur la technique générale consistant à montrer qu'il est possible d'exécuter Rule 110
• L'explication suit l'ordre suivant : boucles, FizzBuzz, puis implémentation de Rule 110

Implémentation

Construction d'une boucle

• Le code suivant crée récursivement des répertoires et produit une boucle infinie

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

• find x énumère les fichiers sous x, et lorsque x est énuméré, il crée x/x
• Pour limiter la profondeur de création des répertoires, on peut utiliser l'option -maxdepth

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

FizzBuzz

• En utilisant l'option -regex de find pour filtrer les noms de fichiers, puis en la combinant avec la boucle, on peut implémenter 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"
  

Implémentation de Rule 110

• Une fois qu'il est possible d'utiliser des boucles et des branchements conditionnels, on peut écrire un programme arbitraire
• Cela est démontré en implémentant 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 \;
  

Questions et réponses prévisibles

• Les limites de longueur des chemins de fichiers empêchent-elles d'exécuter un automate de taille arbitraire ?

  • mkdir échoue si on lui passe un chemin de fichier au-delà d'une certaine longueur, mais le code ci-dessus l'évite
  • find fonctionne même avec des chemins dépassant 30000 caractères

• Le fonctionnement du code ci-dessus est-il garanti par la spécification POSIX ?

  • Non, car le comportement n'est pas spécifié si des fichiers sont ajoutés pendant la traversée d'un répertoire
  • Versions des outils utilisées :

    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
    

Résumé de GN⁺

• La tentative de démontrer la complétude de Turing en n'utilisant que les commandes find et mkdir est intéressante
• L'approche consistant à le prouver via une implémentation de Rule 110 est créative
• Le comportement n'est pas garanti par la spécification POSIX, mais cela fonctionne avec les outils GNU
• Des projets aux fonctionnalités similaires incluent sed et awk