Die Turing-Vollständigkeit von `find` und `mkdir`

Überblick

• Ein Versuch zu beweisen, dass ein System allein mit den GNU-Befehlen find und mkdir turing-vollständig ist
• Dass die Befehle sed und awk turing-vollständig sind, ist allgemein bekannt, aber es gibt keine Referenzen zur Turing-Vollständigkeit von find und mkdir
• Der Beweis verwendet die übliche Technik, zu zeigen, dass sich Rule 110 ausführen lässt
• Die Erklärung folgt der Reihenfolge: Schleifen, FizzBuzz und Implementierung von Rule 110

Implementierung

Aufbau einer Schleife

• Der folgende Code erstellt rekursiv Verzeichnisse und erzeugt eine Endlosschleife

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

• find x listet Dateien unter x auf, und sobald x aufgelistet wird, wird x/x erzeugt
• Um die Tiefe der Verzeichniserstellung zu begrenzen, kann die Option -maxdepth verwendet werden

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

FizzBuzz

• Mit der Option -regex von find werden Dateinamen gefiltert und in Kombination mit der Schleife FizzBuzz implementiert

  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"
  

Implementierung von Rule 110

• Sobald Schleifen und bedingte Verzweigungen verfügbar sind, lassen sich beliebige Programme schreiben
• Dies wird durch die Implementierung von Rule 110 bewiesen

  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 \;
  

Erwartete Fragen und Antworten

• Lässt sich wegen der Begrenzung der Dateipfadlänge kein Automat beliebiger Größe ausführen?

  • mkdir schlägt fehl, wenn ein Dateipfad ab einer bestimmten Länge übergeben wird, aber der obige Code umgeht dies
  • find funktioniert auch bei Pfaden mit mehr als 30000 Zeichen

• Ist garantiert, dass der obige Code gemäß der POSIX-Spezifikation funktioniert?

  • Nein; wenn während der Verzeichnissuche Dateien hinzugefügt werden, ist das Verhalten nicht spezifiziert
  • Verwendete Tool-Versionen:

    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
    

Zusammenfassung von GN⁺

• Der Versuch, Turing-Vollständigkeit allein mit den Befehlen find und mkdir zu beweisen, ist interessant
• Der Ansatz, dies über eine Implementierung von Rule 110 zu zeigen, ist kreativ
• Eine Funktionsgarantie nach POSIX gibt es nicht, aber mit GNU-Tools funktioniert es erfolgreich
• Projekte mit ähnlicher Funktionalität sind sed und awk