Bierdeckelnotation

Die sogenannte Bierdeckelnotation ist eine Darstellung natürlicher Zahlen im Unärsystem. Zur Darstellung jeder beliebigen Zahl wird nur ein Zeichen (Strich auf Bierdeckel) verwendet. Die Bierdeckelnotation orientiert sich dabei an der Strichliste, wie sie bei der Bestellung von Bieren auf dem Bierdeckel geführt wird.

Die natürlichen Zahlen (Anzahl der Biere) werden so notiert, dass ihr Wert der Anzahl eines beliebigen vorher festgelegten Terminalzeichens (z.B. 1) entspricht. Aufgrund der Beliebigkeit des einzigen Symbols im verwendeten Alphabetes gibt es unendlich viele Bierdeckelnotationen.

So ist etwa eine mögliche Bierdeckelnotation der Zahl 6 "111111".

Definition

Es sei $\Sigma\!$ ein einelementiges Alphabet, d. h. $n=card(\Sigma)=1\!$ und $\Sigma^\ast\!$ die Kleenesche Hülle von $\Sigma\!$.

Es sei $\sigma_{BN} : \Sigma^\ast \rightarrow \N\!$ eine totale surjektive Funktion. Für $i \in \N\!$ sei:

$\sigma_{BN}(\varepsilon):=0\!$

$\sigma_{BN}(s^i):=i\!$ (wobei $s \in \Sigma\!$ und $s^i\!$ die $i\!$-fache Konkatenation des Symbols $s\!$ ist).

Dann heißt $\nu_{BN} : \N \rightarrow \Sigma^\ast\!$, definiert durch $\nu_{BN} := \sigma_{BN}^{-1}\!$, eine Bierdeckelnotation von $\Sigma^\ast\!$.

Beispiele

$\sigma_{BN}(111111) = 6\!$

$\sigma_{BN}(11) = 2\!$

$\nu_{BN}(2) = 11\!$

Besonderheiten

Wegen einiger Besonderheiten der Darstellung von Zahlen in Bierdeckelnotation ist diese Darstellung bei einigen Betrachtungen der theoretischen Informatik von Nutzen.

• Nur ein Zeichen wird zur Darstellung benötigt. Das vereinfacht das zu betrachtende Alphabet bei Berechnungen.
• Zeichen haben keine stellenabhängige Bedeutung. Bei der Zahl 123 (dezimal) hat die 1 die Bedeutung der Hunderter, die 3 die der Einer. Entfernt man eine Ziffer, z. B die 3, dann bleibt eine 12 übrig. Die 1 hat jetzt die Bedeutung der Zehner. Dieses Problem tritt bei der Bierdeckelnotation nicht auf. Die Bedeutung der Ziffern ist damit kontextfrei.
• Additionen und Subtraktionen vereinfachen sich (aus Sicht der Notation, nicht aus Sicht der zu schreibenden Zeichen). Zwei Summanden werden addiert, indem man die Zahlen einfach hinter einander schreibt. Beispiel: 8 + 5 = 13 in Bierdeckelnotation ist 11111111 + 11111 = 1111111111111. Zum Vergleich: im Dezimalsystem kann man nicht 8 + 5 = 85 schreiben. Bei theoretischen Betrachtungen bietet diese Eigenschaft den Vorteil, dass die bei einer Addition einmal geschriebenen Ziffern nicht mehr geändert werden müssen.
• Zwischenspeicherung von Zahlen bei abstrakten Maschinen ist seltener nötig. Beispiel: Zwei Zahlen beliebiger Größe sollen mit Hilfe einer abstrakten Maschine, z. B. einer Turingmaschine, addiert werden. Die Maschine habe zwei Eingabebänder, auf der die Summanden stehen und die - ähnliche einer Computertastatur - nur einmalig gelesen werden können, und ein Ausgabeband, auf das, ähnlich wie bei einem Drucker, nur geschrieben werden kann. Sind die Zahlen bierdeckel-codiert, dann vereinfacht sich der Algorithmus zu: Kopiere das erste Eingabeband auf das Ausgabeband und kopiere anschließend das zweite Eingabeband auf das Ausgabeband. Gelesene Zeichen müssen nicht zwischengespeichert werden und brauchen auch nur einmal gelesen werden. Die Addition erfolgt kontextfrei. Zum Vergleich ist eine Addition im Dezimalsystem erheblich komplizierter. Wenn wir beispielsweise 123+456 (=579) berechnen wollen, dann müssen beide Zahlen komplett eingelesen werden und zwischengespeichert. Nur so kann man feststellen, dass die 1 aus 123 und die 4 aus 456 eine gemeinsame "Hunderterbedeutung" haben und daher addiert werden können und die Summe, hier 5, nicht durch die Addition der nachfolgenden Ziffern nach oben verändert wird.
• Eine Zahl ist gleich der Stellenzahl der Darstellung in Bierdeckelnotation. Damit wird diese Darstellung schnell unhandlich. Deshalb findet die Bierdeckelnotation praktische Anwendungen nur bei kleinen Zahlen (Anzahl der auf einem Bierdeckel markierten Biere). Eine praktische Bedeutung hat sie meist dort, wo es leicht sein muss, die Zahl um 1 zu erhöhen ohne damit das bisher Geschriebene zu ändern. (Bei einem neuen Strich auf einem Bierdeckel werden die bisherigen nicht geändert.) Wegen der hohen Stellenzahl kommt der Bierdeckelnotation im allgemeinen eher eine Bedeutung bei theoretischen Betrachtungen der Berechenbarkeitstheorie zu.

Literatur

• Christian Wagenknecht, Michael Hielscher: Formale Sprachen, abstrakte Automaten und Compiler Vieweg, Braunschweig Wiesbaden, 2009