Modul 3

Aufgaben

Literatur
Die Module

Collatz-Automat

Automateneinbettung eines Algorithmus

Der Begriff ''deterministischer Automat'' (dA) ist entstanden als abstraktes Modell realer diskontinuierlich (zeitdiskret, getaktet) und determiniert arbeitender informationeller Systeme mit Eingabe-, Ausgabe-, Verknüpfungs- und Speicherelementen als Träger informationeller Prozesse.

Der dA ist zugleich aber auch ein Notierungssystem mit integrativem, konstruktivem und heuristischem Charakter für eine beträchtliche Anzahl von Algorithmen.

Die Einbettung von Algorithmen in das mathematische Modell dA ist ein nützliches Werkzeug für systematische Erweiterungen, Verallgemeinerungen, Kombinationen, ... von Algorithmen unter Einvernahme des theoretischen und ingenieurmäßig-pragmatischen Methodeninventars für die Analyse und Synthese von Automaten (Schaltbilddenken, Einfügen zusätzlicher Rückkopplungen, Zusammenschaltungen, Zustandskopplungen; vgl. [1], Abschn. 4 und [2], Abschn. 2.3). Vielfach ergibt sich dabei zwanglos die Hinzunahme eines zunächst nicht vorhandenen Schalt- bzw. Steuereingangs (Analogie: Diode Transistor).
Ein dA wird durch nachstehendes Blockschema Bild 1 symbolisiert.

Bild 1: Blockschaltbild des dA

Hierbei ist
- Eingangsvariable Eingangsmenge/Eingabealphabet(1)
- Ausgangsvariable Ausgangsmenge/Ausgabealphabet(2)
- Zustandsvariable Zustandsmenge/internes Alphabet(3)
- Taktzeitpunkt (4)
- (eindeutige)- Ergebnisabbildung,(5)
   Elementnotation
- (eindeutige) Folgezustandsabbildung,(6)
   Elementnotation
- Anfangszustand.(7)
beschreibt die sequentielle, äquidistant getaktete und deterministische Umformung einer Eingangsfolge (eines Eingabewortes)
(8)
in eine Ausgangsfolge (ein Ausgabewort)
(9)
Dabei wird in jedem Taktzeitpunkt (fester aber beliebiger Zeitwert) aus dem einlaufenden Eingangswert und dem im Zeitintervall ''im dA gespeicherten'' Zustandswert

Bild 2: Arbeitsregime des dA

Beispiel:

Verzögerungselement erster Ordnung (D1), Bild 3

Bild 3: Verzögerungselement erster Ordnung
X = Y = Z(10)
y = r (x, z) = z(11)
z' = s (x, z) = x (12)
Jeder Eingangswert erscheint um einen Takt verzögert als am Ausgang, er wird als Zustandswert für einen Takt in D1 gespeichert, und sind dabei vollständig entkoppelt.

Die Collatz-Folge <cn > ist durch das rekursive Bildungsgesetz
(13)
und das Anfangsglied
(14)
erklärt.
Bild 4 zeigt den Verlauf dieser Folge für die Anfangsglieder c0=26 bzw. c0=27.


Bild 4: Verlauf der Collatz-Folge für

Für den Fall c0=26 zeigt die zugehörige Folge <cn > einen kurzen, undifferenzierten und kleinamplitudigen ''Einschwingvorgang'' mit anschließendem periodischen Verlauf .
Der Startwert c0=27 hingegen initiiert eine Folge <cn > mit einem längeren großamplitudigen Einschwingvorgang, der bei spektrumförmigem Verlauf ausgeprägte hohe Peaks besitzt und schließlich ebenfalls in den periodischen Verlauf mündet. Dabei haben beide Folgen bereits vorher eine kurze Werteverlaufsüberdeckung:
(15)
Ähnliche experimentelle Ergebnisse erhält man für alle anderen Initialisierungen , wobei die <cn >-Verläufe sehr stark von c0 abhängen (vgl. vorstehende Beispiele). Höchstwahrscheinlich münden alle diese Folgen in den periodischen Verlauf (für nachgewiesen (vgl. auch [1,2]), ein allgemeiner Beweis ist bisher nicht bekannt).

Anmerkungen:

Der Algorithmus zur Bildung der Collatz-Folge, Gln. (13) und (14), wird nun gemäß Tabelle 1 in das mathematische Modell dA eingebettet.
Dadurch entsteht zunächst ein dA ohne Eingangsgröße x(t) (autonomer dA) mit dem zuvor beschriebenen Collatz-Verhaltensmuster.
Die Hinzunahme eines Steuereinganges und einer einfachen Erweiterung der Folgezustandsabbildung führt zu dem Collatz-Automaten Bild 5.

Bild 5: Collatz-Automat

CO=(X,Y,Z,R,S,z(0))

(16)
mit
(17)
y = r (x, z) = z (18)
 
z' = s (x, z) = co (x + z) (19)

Bereits bei konstanter Eingabe
(20)

Algorithmus zur Bildung
der Collatz-Folge		 -
-
dA


t - z(0) z(t) z(t+1)=s(x(t),z(t))
          =co(z(t))		 y(t)=r(x(t),z(t))
      =z(t)

Tabelle 1: Automateneinbettung des Algorithmus zur Bildung der Collatz-Folge

Bild 6: Ausgangsfolge y(t) des Collatz-Automaten für x(t)=1000 und z(0)=11

Der Collatz-Automat mit konstanter Eingabe a stellt also einen Generator für spektrumförmige Testsignale dar,

Mittels zweier verschiedener synchron laufender Collatz-Automaten mit den Ausgaben y1(t) bzw. y2(t) lassen sich auch interessante Schwarz-Weiß-Muster

pset(y1(t),y2(t))

(21)
erzeugen.

3.1.

Untersuchen Sie experimentell die Verläufe der Ausgangsgröße y(t) des Collatz-Automaten für verschiedene charakteristische Verläufe der Eingangsgröße x(t): und verschiedene Initialisierungen z(0).
Analysieren Sie die auftretenden Verhaltensmuster.

3.2.

Untersuchen Sie experimentell die Verläufe der Ausgangsgröße des Collatz-Automaten für
(22)
(23)
bei verschiedenen , d.h. die Wirkung einer kleinen, auf einen Taktzeitpunkt beschränkten ''Störung'' 1 des konstanten Inputs auf den Output im eingeschwungenen Fall . Die Bilder 7 und 8 zeigen zwei Beispiele.

Bild 7: Ausgangsfolge des Collatz-Automaten für gemäß Gl. (22), , kleine Störung bei
Bild 8: Ausgangsfolge des Collatz-Automaten für gemäß Gl. (22), , kleine Störung bei

Analysieren Sie das ''Störungsgeschehen'' anhand

Diskutieren Sie mögliche Anwendungen des hier betrachteten Verhaltensmusters:

3.3

Bearbeiten Sie die Fragestellungen der Aufgaben 3.1 und 3.2 für den parametrisch erweiterten Collatz-Automaten
(24)
(25)
(26)
(27)
Ergeben sich hier prinzipiell neuartige Verhaltensmuster?

3.4

Bearbeiten Sie die Fragestellungen der Aufgaben 3.1 und 3.2 für die modifizierten Collatz-Automaten
(28)
(29)
(30)
(31)
(32)
(33)
(34)
(35)
und diskutieren Sie die beobachteten Verhaltensmuster.

3.5

Suchen Sie nach Bildungsgesetzen für Zahlenfolgen, die Collatz-ähnliches Verhalten zeigen.
Bearbeiten Sie die Fragestellungen der Aufgaben 3.1 und 3.2 für die zugehörigen dA.

Aufgaben |  Literatur
Die Module