Søren in Norwegen

Neulich stolperte ich ueber einen Artikel in dem der Autor Systeme vorstellte, die ueberraschend Turing-vollstaendig sind. Einige davon waren extrem technische Sachen (wie zum Beispiel das geschickte Rumschieben von Arbeitsspeicher). Andere Beispiele sind (mehr oder weniger) weithin bekannt (bspw. Computerspiele wie Minecraft oder Dwarf Fortress oder natuerlich die meisten (aber nicht alle) Programmiersprachen).
Und dann waren da ein paar Beispiele die ich so cool fand, dass ich die Idee dieses Artikels klaue als Inspiration nehme und daraus eine Miniserie mache.

Heute aber nur eine Einfuehrung, denn mich duenkt ich sollte wenigstens kurz darauf eingehen, was Turing-Vollstaendigkeit eigentlich bedeutet.

In kurz ist ein System Turing-vollstaendig, wenn die Regeln dieses Systems benutzt werden kønnen um jeden beliebigen Computeralgorithmus zu implementieren. Das wichtige an einem Computeralgorithmus ist, dass dieser eine endliche Anzahl von Instruktionen hat um eine Eingabe zu bearbeiten.

Nebenbemerkung: eine endliche Anzahl von Instruktionen bedeutet NICHT, dass besagter Algorithmus jemals endet — unendliche Schleifen møgen dies verhindern. Das ist das sogenannte Halteproblem … eines der der ersten Probleme die im allgemeinen Fall als unentscheidbar erkannt wurden. Aus gegebenem Algorithmus und Eingabe kann man im allgemeinen NICHT erkennen, ob das Programm jemals zum Ende kommt.
In vielen konkreten Faellen kann man das aber sehr wohl entscheiden. In Faellen wo es wichtig ist, dass eine Berechnung terminiert, werden sogar Programmiersprachen benutzt die bspw. unendliche Schleifen automatisch beenden, Solche Programmiersprachen sind dann aber meines Wissens nach meist NICHT Turing-vollstaendig (denn sie kønnen ja nicht jeden Computeralgorithmus ausfuehren).

Wenn ein System Turing-vollstaendig ist, so bedeutet das auch, dass dieses System jedes beliebige andere Turing-vollstaendige System emulieren kann … oder leichter einzupraegen: Can it run DOOM? … und die Antwort ist vermutlich: Yes, it can.

Aber Achtung! Turing-Vollstaendigkeit heiszt NICHT dass oben erwaehnte Emulierung einfach zu implementieren ist oder schnell laeuft oder konkret (wenn auch theoretisch) møglich ist. Die ersten beiden Einschraenkungen sind intuitiv zu verstehen. Die Letzte folgt daraus, dass Turing-Vollstaendigkeit eigentlich unendlich viel Arbeitsspeicher voraussetzt. Fuer alle praktischen Belange wird das ignoriert. Es kann dann aber doch der Grund sein, warum eine konkrete Emulierung nicht zu implementieren ist. Oder anders: DOOM laeuft heutzutage auf echt vielen Geraeten, das bedeutet aber nicht, dass man auf den selben Geraeten auch ein vollstaendiges Linux mit Multimedia- und Internetanwendungen laufen lassen kønnte.

So, das war jetzt alles aus der Welt der Computer. Dies deswegen, weil die Eigenschaft der Turing-Vollstaendigkeit dort „erfunden“ wurde und am einfachsten zu verstehen ist. In dieser Miniserie werde ich aber auch aus der Computerwelt heraus treten. Damit verbleibe ich bis zum naechsten Mal.