- Avec
find et mkdir de GNU seulement, on peut créer des boucles et des transitions d’état en exploitant la création de répertoires et l’ordre de parcours, si bien qu’une simple combinaison d’utilitaires de fichiers devient un modèle de calcul
- La démonstration passe par l’implémentation d’un système de tags (tag system), et la première preuve fondée sur Rule 110 a été corrigée en raison d’un problème de gestion des répétitions infinies
- La boucle de base repose sur le fait que
find x -execdir mkdir x/x \; continue de découvrir de nouveaux répertoires, et l’ajout de -regex permet même des branchements conditionnels de type FizzBuzz
- L’implémentation du système de tags représente l’état par des chemins de fichiers et copie le reste après suppression des
m premiers caractères au moyen de back-references
- POSIX laisse le comportement non spécifié lorsqu’un fichier est ajouté dans un répertoire en cours d’exploration ; la conclusion dépend donc du comportement observé des outils GNU et de l’environnement présenté
Construire un modèle de calcul avec GNU find et mkdir
- L’objectif est de montrer qu’un système disposant uniquement des commandes GNU
find et mkdir est Turing-complet
- La preuve procède en implémentant un système de tags
- Le déroulé général suit l’ordre suivant : construction d’une boucle, FizzBuzz, puis implémentation d’un système de tags
- L’erreur de la première version de la preuve fondée sur Rule 110, datée du 2 août 2024, a été corrigée, et la version actuelle repose désormais sur l’implémentation d’un système de tags
- La première version ne parvenait pas à traiter un nombre infini de répétitions
- L’article associé, Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation, a été accepté à FUN with Algorithms 2026
La boucle produite par la création de répertoires
- Le code suivant crée récursivement des répertoires et entre dans une boucle infinie
mkdir x
find x -execdir mkdir x/x \;
find x énumère les fichiers sous x, y compris x lui-même- Lorsque
x est énuméré, mkdir crée x/x, et à l’itération suivante de find, le nouveau x/x est inclus
- À mesure que ce processus se répète, des chemins comme
x/x/x, x/x/x/x continuent d’être créés
- L’option
-maxdepth permet de limiter la profondeur de création
mkdir x
find x -maxdepth 3 -execdir mkdir x/x \;
- Cet exemple se termine après avoir créé
x/x/x/x/x
FizzBuzz implémenté avec find -regex
- L’option
-regex de find peut filtrer les noms de fichiers qui seront visés par les actions suivantes
- En combinant ce filtre avec la boucle, on peut implémenter un FizzBuzz qui détermine si le nombre de
x/ est un multiple de 3, 5 ou 15
- Pour la lisibilité, l’exemple utilise
-regextype posix-extended, mais l’idée serait applicable de la même manière avec d’autres syntaxes d’expressions régulières
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 deuxième ligne génère sous
d un chemin contenant 30 x consécutifs
- La troisième ligne affiche
FizzBuzz si le nombre de x est un multiple de 15, Buzz s’il est multiple de 5, Fizz s’il est multiple de 3, et sinon la profondeur à partir de d
- Le résultat d’exécution est visible dans cet exemple OneCompiler
Montrer la complétude de Turing via un système de tags
- Un système de tags est défini par
(m, A, P)
m est un entier positifA est un alphabet fini contenant le symbole d’arrêt HP est la règle de production de chaque symbole de l’alphabet
- Étant donné une chaîne initiale, le système répète le processus suivant
- Si la longueur de la chaîne est inférieure à
m, ou si son premier caractère est H, il s’arrête
- Sinon, il ajoute
P(x) à la fin de la chaîne pour le premier caractère x
- Il supprime ensuite les
m premiers caractères
- On sait qu’un système de tags avec
m=2 et |A|=576 est une machine de Turing universelle ; tout système capable d’exécuter un tel système de tags est donc Turing-complet
- L’exemple d’implémentation concret utilise le simple système de tags à 2 symboles
m=2, |A|=4, présenté sur Wikipedia
Utiliser des chemins de fichiers comme état
- L’idée centrale consiste à continuer d’ajouter l’état suivant à la fin d’un chemin de fichier représentant l’état courant
_ sert de séparateur entre les états
- Exemple :
_/b/a/a/_
- Si l’état suivant est
a/c/c/a, le chemin devient _/b/a/a/_/a/c/c/a/_
- L’implémentation est conçue de sorte qu’il n’y ait jamais plus d’un fichier dans un même répertoire pendant l’exécution
- Elle continue d’ajouter l’état suivant jusqu’à rencontrer le symbole d’arrêt ou jusqu’à ce que la longueur de la chaîne devienne inférieure ou égale à
m
- L’expression conditionnelle de
find fonctionne globalement en trois parties
- Vérification de la condition d’arrêt
- Copie du reste de l’état précédent après suppression des
M premiers caractères à l’aide de back-references
- Application des règles de production pour
a, b et c
- Les règles de production d’exemple sont les suivantes
M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"
- Le résultat attendu à l’exécution est
_/H/c/c/c/c/c/c/a/_
- Ce résultat est lui aussi fourni dans un exemple OneCompiler
Back-references et extensibilité
- L’implémentation de FizzBuzz utilise des expressions régulières ordinaires, mais celle du système de tags emploie la back-reference
\2
- Grâce à cette back-reference, il est possible de recopier depuis l’état précédent tout ce qui suit les
m premiers caractères
- Cette construction peut être étendue à un alphabet de taille constante plus grande
- S’il n’y a pas assez de caractères disponibles, on peut utiliser plusieurs caractères par nom de fichier au lieu d’un seul
- On aboutit ainsi à la conclusion que la combinaison
find + mkdir est Turing-complète
Contraintes POSIX et environnement d’exécution
- À cause des limites de longueur des chemins, il est possible qu’on ne puisse pas exécuter un automate de taille arbitraire, mais le code présenté est conçu pour ne pas transmettre directement à
mkdir des chemins de longueur arbitraire
- Lors des tests,
find a fonctionné sur des chemins dépassant 30 000 caractères, et aucune limite distincte n’a été trouvée
- Il n’existe toutefois aucune garantie POSIX
- La documentation POSIX de
find précise que le comportement est non spécifié lorsque des fichiers sont ajoutés dans un répertoire pendant son exploration
- Le comportement d’outils autres que GNU n’a pas été vérifié
- L’environnement utilisé était le suivant
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 commentaires
Avis de Hacker News
C’est déjà écrit tout en haut de la page : l’affirmation selon laquelle find + mkdir sont Turing-complets a été retirée
Il est indiqué que, la preuve étant défectueuse, l’auteur retire l’affirmation selon laquelle il aurait prouvé que find + mkdir sont Turing-complets, et renvoie vers https://news.ycombinator.com/item?id=41117141
Il est aussi indiqué que l’article sera mis à jour si la preuve peut être corrigée
Peut-on implémenter Folders avec ça ?
https://www.danieltemkin.com/Esolangs/Folders/
Les entrées de répertoire occupent de l’espace dans la MFT, mais Explorer ne compte que les blocs alloués ailleurs, donc cela n’apparaît pas
Si l’on continue à créer des répertoires vides, la MFT grossit et finit par poser un problème d’espace
C’est similaire pour les petits fichiers : un fichier texte vide apparaît avec une taille de 0 octet et une taille sur disque de 0 octet ; même si l’on y met environ 400 octets, les données tiennent dans l’entrée de répertoire de la MFT préallouée, et Explorer affiche donc une taille sur disque de 0
Si l’on double les données, un bloc disque est alloué et le fichier apparaît avec une longueur de 800 octets et une taille sur disque de 4 096 octets ; si on le réduit ensuite à 400 octets, les données ne retournent pas dans la MFT et continuent d’occuper 4 096 octets
Cela n’empêche toutefois pas d’apprécier l’ensemble, qui reste un excellent résultat
Je ne comprends pas en quoi cela montre la complétude de Turing
L’implémentation de l’automate règle 110 semble se heurter à la limite de largeur, ainsi qu’à la limite du nombre d’itérations
Le nombre d’états pour une largeur donnée est fini, donc ce n’est pas Turing-complet ; et comme cela termine toujours, ce n’est pas non plus Turing-complet
Peut-on écrire une implémentation de la règle 110 avec une largeur et une profondeur arbitraires, c’est-à-dire extensibles à l’infini ?
Les vrais ordinateurs n’ont pas non plus de ruban infini, mais une mémoire finie ; ils ne satisfont donc pas cette condition, quel que soit le langage ou la méthode
Il est indiqué que l’article sera mis à jour si la preuve peut être corrigée
Retiré
Il est écrit : « la preuve étant défectueuse, je retire l’affirmation selon laquelle j’ai prouvé que find + mkdir sont Turing-complets »
Je m’attendais à une forme intéressante de lambda-calcul, mais en réalité cela dépendait simplement du parseur d’expressions régulières de find pour effectuer le calcul
Un exemple qui me revient en mémoire est http://realgl.blogspot.com/2013/08/battlecode.html ; voir la partie « Regular Expression Pathfinding »
Cette preuve serait probablement beaucoup plus simple en utilisant un système de tag (https://en.m.wikipedia.org/wiki/Tag_system) plutôt qu’un automate cellulaire
Aucune implémentation ne peut être infinie, mais dans ce cas, PATH_MAX, dont la valeur habituelle est 4096, paraît particulièrement bas
Sous GNU, cela semble fonctionner même avec des chemins de plus de 4096 caractères
apparently, l’auteur dit avoir testé jusqu’à une longueur de chemin de 30k
Les logiciels ou services qui implémentent ou consomment des expressions régulières (RE, RegExp), ou les composants au sein d’une chaîne de logiciels/services, peuvent potentiellement être Turing-complets
Si la sécurité est importante dans ce contexte, il faut auditer leur complétude de Turing
Pour obtenir la complétude de Turing, il faut deux piles
Cela dit, beaucoup de bibliothèques d’expressions régulières prennent en charge bien plus de fonctionnalités que de simples « expressions régulières »
Mon find n’est pas seulement prouvablement Turing-complet : ce n’est même pas un Turing tarpit, et il est compilé en code natif