Website von

Jan Schejbal

Server Side Includes sind Turing-vollständig

Mein Hoster bietet in dem günstigen Paket, welches ich gebucht habe, kein PHP an - dafür aber Server Side Includes (mit denen auch diese Website gemacht ist). Zunächst hatte ich erwartet, die Sprache würde nur ganz einfache Einbindungen unterstützen, doch sie enthält auch Bedingungen und Variablen. Da man über die Includes auch eine Rekursion hinbekommt, habe ich mich gefragt, ob die Sprache Turing-vollständig ist. Turing-Vollständigkeit bedeutet, sehr vereinfacht gesagt, dass man damit beliebige Programme schreiben kann. (Da man keinen Zugriff auf Ressourcen wie Netzwerk und Festplatte hat, wird man in der Praxis damit allerdings nicht weit kommen. Das hist ist also eigentlich nur Informatiker-Spielerei.) Eine Google-Suche hat keine brauchbaren Ergebnisse gebracht - es gab also nur noch einen Weg, es herauszufinden: Ausprobieren!

Eine Sprache ist Turing-vollständig, wenn man eine Turing-Maschine darin implementieren kann. Also dann, an die Arbeit. Eine Turing-Maschine hat Eine Turing-Maschine unterstützt in jedem Schritt folgende Möglichkeiten:

Implementiert ist dieser Teil in step.shtml. Zunächst werden für jeden Schritt temporäre Variablen initialisiert und dann wird das gewählte Programm (d.h. die Funktion, die sich um die Zustandsübergänge und Aktionen kümmert) aufgerufen. Das Programm hat Zugriff auf den Zustand und das aktuelle Bandzeichen und schreibt in die entsprechenden Variablen, ob etwas geschrieben werden soll, ob und in welche Richtung das Band bewegt werden soll, ob das Programm anhalten soll und was der nächste Zustand ist. Die Befehle werden dann von step.shtml umgesetzt und der Zustand der Maschine und des Bands wird ausgegeben.

Zum Schluss muss noch sichergestellt werden, dass dieser Schritt immer wieder bis zum Anhalten der Maschine ausgeführt wird. Da in SSI keine Schleifen möglich sind, gibt es zwei Möglichkeiten: Eine große Datei anlegen, die immer wieder step.shtml included (dann ist die Anzahl der Schritte begrenzt), oder Rekursion - eine Datei ruft immer wieder sich selbst (und bei jedem Aufruf einmal step.shtml) auf. Rekursion ist theoretisch unendlich, stößt jedoch nach wenigen Schritten meist an eine Beschränkung im Webserver. Daher werden im Beispielcode beide Möglichkeiten unterstützt.

Die Maschine wird über run.shtml aufgerufen. Dort kann das Programm angegeben werden. Aus dem Unterordner mit dem Programmnamen wird dann zunächst die Initialisierung durchgeführt (per Aufruf von init.shtml), später wird step.shtml das Programm (program.shtml) von dort ausführen. Auch der Modus (rekursiv oder iterativ) kann gewählt werden. Abhängig davon wird anschließend run_recursive.shtml oder run_iterative.shtml eingebunden, deren Funktionsweise oben erklärt wurde. Diese rufen dann wiederum step.shtml auf.

Demo und Download

Die SSI-Turingmaschine kann man mit dem berühmten Fleißigen Bieber (mit zwei Zuständen, ich möchte meinen Hoster nicht unnötig belasten) hier ausprobieren. Den Quellcode gibt es hier zum Herunterladen auf eigene Gefahr zur privaten nichtkommerziellen Nutzung.

Server Side Includes are Turing complete

My webhost does not offer PHP in the cheap package I ordered - but they do offer Server Side Includes (which is also what I use for this web site). At first I was expecting that the language will just support simple includes, but it also contains conditions and variables. As you can do recursion using the includes, I asked myself if the language is Turing complete. Turing completeness means, very simplified, that you can write any program with it. (However, as you do not have access to ressources like network and hard disk, you will not be able to do much with it in practice. This is just a just-for-fun computer science thing.) A google search did not turn up anything useful, so there was only one way to find out: Trying it!

A language is Turing complete, if you can use it to implement a Turing machine. So, lets get started. A Turing machine has In every step, a Turing machine supports the following actions:

This part is implemented in step.shtml. First, for every step temporary variables are initialized, and then the selected program (i.e. the function taking care of the state changes and actions) is called. The program has access to the state and the current character and writes to the corresponding variables if something has to be written, if (and in what direction) the tape is to be moved, if the program should halt and what the next state is. The commands are then executed by step.shtml and the state of the machine and the tape is printed.

Finally, it has to be ensured that this step is repeatedly executed until the machine halts. As SSI does not support loops, there are two options: Creating a large file, that includes step.shtml many times (then the number of steps is limited), or recursion - a file incudes itself again and again and every time it gets included, it includes step.shtml once. Recursion is theoretically unlimited, but usually hits a limit in the web server after a few steps. For this reason, the example code supports both methods.

The machine is started via run.shtml. Inside that file, the program name can be defined. From the subdirectory bearing the program name, first the initialization (init.shtml) is run, and later, step.shtml will call the program (program.shtml) from there. The mode (recursive or iterative) can also be selected. Depending on that setting, either run_recursive.shtml or run_iterative.shtml is then inlcuded (their mode of operation was explained above). Those then call step.shtml.

Demo and download

The SSI Turing machine can be seen in action running the famous Busy Beaver (with two states, I do not want to cause unnecessary load on my web host) here. The source code can be downloaded here for personal noncommercial use at your own risk.