- Schon nur mit GNU-
find und mkdir lassen sich durch das Erzeugen von Verzeichnissen und die Reihenfolge ihrer Traversierung Schleifen und Zustandsübergänge konstruieren, sodass die Kombination einfacher Datei-Utilities zu einem Berechnungsmodell wird
- Der Beweis erfolgt über die Implementierung eines Tag-Systems; der erste, auf Rule 110 basierende Beweis wurde wegen eines Problems bei der Behandlung unendlicher Wiederholungen korrigiert
- Die grundlegende Schleife ist eine Struktur, in der
find x -execdir mkdir x/x \; ständig neue Verzeichnisse entdeckt; mit -regex sind auch bedingte Verzweigungen wie FizzBuzz möglich
- Die Implementierung des Tag-Systems stellt den Zustand als Dateipfad dar und kopiert mit Back-References den Rest nach dem Entfernen der ersten
m Zeichen
- POSIX lässt das Verhalten beim Hinzufügen von Dateien in ein gerade durchsuchtes Verzeichnis als unspecified offen; die Schlussfolgerung hängt daher vom beobachteten Verhalten der GNU-Tools und der angegebenen Umgebung ab
Aufbau eines Berechnungsmodells mit GNU find und mkdir
- Ziel ist zu zeigen, dass ein System, das nur die GNU-Befehle
find und mkdir besitzt, turing-vollständig ist
- Der Beweis erfolgt durch die Implementierung eines Tag-Systems
- Der Gesamtaufbau verläuft in der Reihenfolge Schleifenkonstruktion, FizzBuzz, Implementierung des Tag-Systems
- Am 2. August 2024 wurde ein Fehler im ersten, auf Rule 110 basierenden Beweis korrigiert; die aktuelle Version verwendet nun die Implementierung eines Tag-Systems
- Die erste Version hatte das Problem, eine unendliche Anzahl von Wiederholungen nicht verarbeiten zu können
- Das zugehörige Paper Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation wurde bei FUN with Algorithms 2026 angenommen
Schleifen durch Verzeichniserzeugung
- Der folgende Code erzeugt rekursiv Verzeichnisse und gerät in eine Endlosschleife
mkdir x
find x -execdir mkdir x/x \;
find x listet die Dateien unter x auf und schließt x selbst ein- Wenn
x aufgelistet wird, erzeugt mkdir x/x, und im nächsten Durchlauf von find wird das neu entstandene x/x einbezogen
- Dieser Prozess wiederholt sich, wodurch fortlaufend Pfade wie
x/x/x, x/x/x/x usw. entstehen
- Mit der Option
-maxdepth lässt sich die Erzeugungstiefe begrenzen
mkdir x
find x -maxdepth 3 -execdir mkdir x/x \;
- Dieses Beispiel beendet sich, nachdem
x/x/x/x/x erzeugt wurde
FizzBuzz mit find -regex
- Die Option
-regex von find kann Dateinamen filtern, auf die die nachfolgenden Aktionen angewendet werden
- In Kombination mit der Schleife lässt sich damit ein FizzBuzz implementieren, das prüft, ob die Anzahl von
x/ ein Vielfaches von 3, 5 oder 15 ist
- Das Beispiel verwendet für bessere Lesbarkeit
-regextype posix-extended, geht aber davon aus, dass dieselbe Methode auch mit anderen Regex-Syntaxen möglich ist
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"
- Die zweite Zeile erzeugt unter
d einen Pfad, in dem x 30-mal hintereinander vorkommt
- Die dritte Zeile gibt bei einer Anzahl von
x, die ein Vielfaches von 15 ist, FizzBuzz aus, bei einem Vielfachen von 5 Buzz, bei einem Vielfachen von 3 Fizz, und sonst die Tiefe relativ zu d
- Das Ausführungsergebnis ist im OneCompiler-Beispiel zu sehen
Turing-Vollständigkeit per Tag-System zeigen
- Ein Tag-System besteht aus
(m, A, P)
m ist eine positive ganze ZahlA ist ein endliches Alphabet, das das Haltesymbol H enthältP sind die Erzeugungsregeln für jedes Symbol des Alphabets
- Für eine gegebene Anfangszeichenkette wiederholt das System den folgenden Prozess
- Ist die Zeichenkette kürzer als
m oder ist ihr erstes Zeichen H, hält das System an
- Andernfalls wird
P(x) für das erste Zeichen x an das Ende der Zeichenkette angehängt
- Die ersten
m Zeichen werden gelöscht
- Es ist bekannt, dass ein Tag-System mit
m=2 und |A|=576 eine universelle Turing-Maschine ist; ein System, das ein Tag-System dieser Größe ausführen kann, ist turing-vollständig
- Das konkrete Implementierungsbeispiel verwendet das einfache 2-Tag-System aus Wikipedia mit
m=2 und |A|=4
Dateipfade als Zustände verwenden
- Die Kernidee besteht darin, hinter einen Dateipfad, der einen Zustand repräsentiert, fortlaufend den nächsten Zustand anzuhängen
- Als Trennzeichen zwischen Zuständen wird
_ verwendet
- Beispiel:
_/b/a/a/_
- Wenn der nächste Zustand
a/c/c/a ist, wird der Pfad zu _/b/a/a/_/a/c/c/a/_
- Während der Ausführung ist das System so aufgebaut, dass sich in einem Verzeichnis nie mehr als eine Datei befindet
- Die Implementierung hängt fortlaufend den nächsten Zustand an, bis das Haltesymbol erreicht wird oder die Zeichenkette höchstens Länge
m hat
- Der Bedingungsausdruck von
find arbeitet im Wesentlichen in drei Teilen
- Prüfung der Haltebedingung
- Kopieren des Rests des vorherigen Zustands nach dem Entfernen der ersten
M Zeichen mithilfe von Back-References
- Anwenden der Erzeugungsregeln für
a, b und c
- Die beispielhaften Erzeugungsregeln lauten wie folgt
M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"
- Als Ausführungsergebnis wird erwartungsgemäß
_/H/c/c/c/c/c/c/a/_ ausgegeben
- Auch dieses Ausführungsergebnis ist als OneCompiler-Beispiel verfügbar
Back-References und Erweiterbarkeit
- Die FizzBuzz-Implementierung nutzt gewöhnliche reguläre Ausdrücke, die Implementierung des Tag-Systems jedoch Back-Reference
\2
- Dank der Back-Reference lässt sich aus dem vorherigen Zustand der Teil nach den ersten
m Zeichen kopieren
- Diese Konstruktion lässt sich auf ein Alphabet konstanter, aber größerer Größe erweitern
- Falls die verfügbaren Zeichen nicht ausreichen, kann man statt einzelner Zeichen längere Dateinamen verwenden
- Daraus folgt die Schlussfolgerung, dass die Kombination
find + mkdir turing-vollständig ist
POSIX-Einschränkungen und Ausführungsumgebung
- Wegen der Begrenzung der Dateipfadlänge könnte es sein, dass kein Automat beliebiger Größe ausgeführt werden kann; der gezeigte Code ist jedoch so aufgebaut, dass kein Dateipfad beliebiger Länge direkt an
mkdir übergeben wird
- In Tests funktionierte
find auch bei Pfaden mit mehr als 30000 Zeichen, und es wurde keine gesonderte Begrenzung gefunden
- Eine Garantie durch POSIX gibt es nicht
- Die POSIX-
find-Dokumentation legt fest, dass das Verhalten unspecified ist, wenn während der Suche Dateien in das durchsuchte Verzeichnis hinzugefügt werden
- Das Verhalten anderer Tools außer GNU wurde nicht überprüft
- Verwendet wurde die folgende Umgebung
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 Kommentare
Hacker-News-Kommentare
Ganz oben auf der Seite steht bereits: Die Behauptung zur Turing-Vollständigkeit von find + mkdir wurde zurückgezogen
Dort heißt es, der Beweis sei fehlerhaft, daher werde die Behauptung zurückgezogen, bewiesen zu haben, dass find + mkdir Turing-vollständig ist; siehe https://news.ycombinator.com/item?id=41117141
Falls der Beweis korrigiert werden kann, soll der Beitrag aktualisiert werden
Kann man damit Folders implementieren?
https://www.danieltemkin.com/Esolangs/Folders/
Verzeichniseinträge belegen Platz in der MFT, werden aber nicht angezeigt, weil der Explorer nur anderswo allozierte Blöcke mitzählt
Wenn man immer weiter leere Verzeichnisse anlegt, wächst die MFT und irgendwann gibt es Speicherplatzprobleme
Bei kleinen Dateien ist es ähnlich: Eine leere Textdatei erscheint mit Größe 0 Byte und Größe auf Datenträger 0 Byte; selbst wenn man etwa 400 Byte hineinschreibt, landen die Daten im bereits vorab allozierten Verzeichniseintrag der MFT, sodass der Explorer weiterhin 0 als Größe auf Datenträger anzeigt
Verdoppelt man die Datenmenge, wird ein Datenträgerblock alloziert und es erscheint eine Länge von 800 Byte sowie eine Größe auf Datenträger von 4.096 Byte; reduziert man sie wieder auf 400 Byte, wandern die Daten nicht zurück in die MFT und belegen weiterhin 4.096 Byte
Das schmälert aber insgesamt nicht den Genuss dieses großartigen Ergebnisses
Ich verstehe nicht, wie das Turing-Vollständigkeit zeigen soll
Die Implementierung des Regel-110-Automaten scheint sowohl an eine Breitenbegrenzung als auch an eine Begrenzung der Iterationszahl zu stoßen
Die Anzahl der Zustände bei gegebener Breite ist endlich, also nicht Turing-vollständig; und da es immer terminiert, ebenfalls nicht Turing-vollständig
Kann man eine Implementierung von Regel 110 mit beliebiger, also unbegrenzt erweiterbarer Breite und Tiefe schreiben?
Auch reale Computer nutzen keinen unendlichen Bandstreifen, sondern endlichen Speicher, erfüllen diese Bedingung also unabhängig von Sprache oder Methode nicht
Falls der Beweis korrigiert werden kann, soll der Beitrag aktualisiert werden
Zurückgezogen
Dort steht: „Da der Beweis fehlerhaft ist, ziehe ich die Behauptung zurück, bewiesen zu haben, dass find + mkdir Turing-vollständig ist“
Ich hatte erwartet, dass eine interessante Form des Lambda-Kalküls verwendet wird, tatsächlich stützte sich das Ganze aber nur für die Berechnung auf den Regex-Parser von find
Ein Beispiel, das mir im Gedächtnis geblieben ist, ist http://realgl.blogspot.com/2013/08/battlecode.html; siehe den Abschnitt „Regular Expression Pathfinding“
Dieser Beweis dürfte deutlich einfacher werden, wenn man statt eines zellulären Automaten ein Tag-System (https://en.m.wikipedia.org/wiki/Tag_system) verwendet
Keine Implementierung kann unendlich sein, aber in diesem Fall wirkt PATH_MAX, dessen üblicher Wert 4096 ist, besonders niedrig
Unter GNU scheint es auch mit Pfadlängen von mehr als 4096 zu funktionieren
Offenbar wurde bis zu einer Pfadlänge von 30k getestet
Software/Services, die reguläre Ausdrücke (RE, RegExp) implementieren oder konsumieren, oder Komponenten innerhalb einer Kette von Software/Services, können potenziell Turing-vollständig sein
Wenn Sicherheit in diesem Kontext wichtig ist, sollte man auditieren, ob Turing-Vollständigkeit vorliegt
Um Turing-Vollständigkeit zu erreichen, braucht man zwei Stacks
Allerdings unterstützen viele Regex-Bibliotheken deutlich mehr Funktionen als einfache „reguläre Ausdrücke“
Mein find ist nicht nur nachweislich Turing-vollständig, sondern auch kein Turing-Tarpit und wird zu nativem Code kompiliert