Lexikon der Mathematik: Zählerautomat
an Rechenmaschinen angelehntes mathematisches Modell zur Formalisierung des Algorithmenbegriffs.
Ein Zählerautomat verfügt über eine endliche Menge von Registern R1, …, Rm, von denen jedes in der Lage ist, eine beliebig große natürliche Zahl zu speichern. Ein Algorithmus wird als endlich lange durchnumerierte Liste von Befehlen notiert. Als Befehle stehen zur Verfügung:
- INCRj → k: (Erhöhe den Wert des Registers Rj um 1 und setze mit dem Befehl an Position k der Befehlsliste fort).
- T&DECRj → k1/k2 : (Falls Rj den Wert 0 speichert, lasse diesen Wert unverändert und setze mit dem Befehl an Position k1 fort, ansonsten verringere den Wert von Rj und setze mit dem Befehl an Position k2 fort);
- STOP: Beende die Programmabarbeitung.
Ein Zählerautomat mit mindestens n + 1 Registern berechnet eine n-stellige partielle zahlentheoretische Funktion f, falls bei Belegung der Register R1, …, Rn mit Funktionsargumenten x1, …, xn und nachfolgendem Start der Programmabarbeitung mit dem Befehl an der ersten Position der Zählerautomat genau dann irgendwann einen STOP-Befehl erreicht, wenn f (x1, …, xn)definiert ist und dann Rn+1 den Funktionswert enthält, während die Programmabarbeitung niemals stoppt, falls f auf den übergebenen Argumenten nicht definiert ist.
Der so gebildete Berechenbarkeitsbegriff ist äquivalent zur Definition von Berechenbarkeit mittels Turing-Maschinen und weiteren Berechenbarkeitsmodellen.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.