Die vier Berechnungsmodelle Zellulärer Automat, Markow-Algorithmus, Post’sches Tag-System und Zählermaschine besitzen die gleiche Berechnungsstärke wie Turingmaschine, Lambda-Kalkül, Random Access Machine und WHILE-Schleife. Ihre Funktionsweise unterscheidet sich größtenteils stark von den aus dem Informatik-Bachelor bekannten Berechnungsmodellen. Der Zelluläre Automat berechnet den folgenden Zellenzustand anhand des vorliegenden Zustands der Zelle und der Zustände der Nachbarzellen, wodurch er auf allen Zellen gleichzeitig (parallel) arbeitet. Der Markow-Algorithmus arbeitet auf Wörtern, wobei er das Eingabewort durch Suchen und Ersetzen jeweils eines Teilwortes umwandelt. Das Tag-System arbeitet auch auf Wörtern, schneidet aber ein Teilwort fester Länge am Anfang des Wortes ab und hängt ein Teilwort am Ende an. Die Zählermaschine ähnelt der Random Access Machine, besitzt aber – je nach Autor – nur drei bis vier Operationen und kann Register nicht indirekt adressieren.

Meine Arbeit vertieft die Funktionsweise der vier Modelle anhand der Erarbeitung des Primzahltests. Das gemeinsame Beispiel erleichtert wiederum den Vergleich zwischen den vier Modellen. Außerdem skizziert sie die Beweise, dass die Modelle turingvollständig sind. Bei meiner Verteidigung werde ich unter anderem auf die vier Modelle und den Primzahltest für den Markow-Algorithmus eingehen.