Was ist eine abstrakte Maschine?
Abstrakte Maschinen, auch Automaten genannt, sind ein Element der theoretischen Informatik. Eine abstrakte Maschine ähnelt einer mathematischen Funktion. Es empfängt Eingaben und erzeugt Ausgaben nach festgelegten Regeln. Abstrakte Maschinen unterscheiden sich von wörtlicheren Maschinen, da angenommen wird, dass sie perfekt und unabhängig von der Hardware funktionieren. Sie werden auf der Grundlage von Merkmalen wie der Art und Weise, wie sie ihre Operationen ausführen und welche Arten von Eingaben sie empfangen können, in Typen unterteilt.
Eine der einfachsten Unterscheidungen bei der Klassifizierung abstrakter Maschinen betrifft die Anzahl der Operationen, die sie zu einem bestimmten Zeitpunkt ausführen dürfen. Eine abstrakte Maschine heißt deterministisch, wenn es immer nur einen Weg gibt, um fortzufahren. Es ist nicht deterministisch, ob für die Maschine in mindestens einem ihrer möglichen Zustände mehrere Möglichkeiten existieren. Ein "Pushdown" -Automat ist einer, der in der Lage ist, seinen Stapel von Eingaben zu manipulieren, anstatt einfach in der Reihenfolge, in der er erscheint, nacheinander darauf zu reagieren.
Wolfram MathWorld gibt zwei berühmte Beispiele für abstrakte Maschinen. Eines dieser Beispiele ist Conways Spiel des Lebens, bei dem es sich um eine deterministische abstrakte Maschine handelt, da aus jeder anderen nur eine Konfiguration hervorgehen kann. In diesem Spiel wird ein Raster verwendet, in dem jede Box oder Zelle entweder den Status "lebend" oder "tot" haben kann. Der Zustand des gesamten Gitters wird auf der Grundlage des vorherigen Zustands bestimmt. Wenn eine lebende Zelle genau zwei oder drei andere lebende Zellen berührt, lebt sie weiter. Wenn es einen, zwei oder mehr als drei Nachbarn hat (bis zu acht), stirbt es. Eine tote Zelle mit genau drei Nachbarn wird zum Leben erweckt; Andernfalls bleibt es tot.
Ein anderes Beispiel, die Turing-Maschine, ist eine der grundlegendsten und grundlegendsten abstrakten Maschinen in der Informatik. Eine Turing-Maschine bearbeitet ein Band - eine Zeichenfolge - mit unbegrenzter Größe. Es enthält Anweisungen zum Ändern der Symbole und zum Ändern des Symbols, auf das es angewendet wird. Eine einfache Turingmaschine hat möglicherweise nur den Befehl "Symbol in 1 umwandeln, dann nach rechts bewegen". Diese Maschine würde nichts als eine Folge von Einsen ausgeben. Diese einfache Turingmaschine ist deterministisch, es ist jedoch auch möglich, nicht deterministische Turingmaschinen zu konstruieren, die bei gleicher Eingabe mehrere verschiedene Operationen ausführen können.
Diese abstrakten Maschinen können vielen Zwecken dienen. Sie können lustige theoretische Spielzeuge sein, aber sie können auch als Modelle für echte Computersysteme dienen. Die abstrakte Maschine ist das Herzstück der Informatik als Disziplin.