.

💡 Nachfolgender Beitrag wurde mittels OCR/KI (xAI) erstellt und weicht vom obigen Original erheblich ab 💡

Ø

§6. WPNC-BERECHENBARKEIT, ZÄHLERAUTOMATEN

Im vorangegangenen Paragraphen haben wir die Auswirkungen von Inhibitor-Kanten auf dimensionsbezogene Semilinearitätsgrenzen studiert. Dennoch sind Inhibitor-Kanten ein Mittel, das qualitativ mehr ermöglicht als nur das Basismodell. Das zeigt sich insbesondere bei der Simulation von Berechnungsvorgängen.

Definition 6.1. (Schwacher Petri-Netz-Computer)

Sei $\backslash mathcal\{P\}$ ein Petri-Netz mit Stellenmenge

mit $X\; =\; \backslash \{x\_1,\; \backslash dots,\; x\_n\backslash \}$ und $R\; =\; \backslash \{r\_1,\; \backslash dots,\; r\_k\backslash \}$.

Für alle Transitionen $t\; \backslash in\; T$ gelte:

• $\backslash kappa(o,\; t)\; =\; 0$
• $\backslash kappa(t,\; x\_j)\; =\; 0$ für alle $x\_j\; \backslash in\; X$
• $\backslash kappa(t,\; s)\; \backslash ge\; \backslash kappa(s,\; t)$

Ein Petri-Netz $\backslash mathcal\{P\}$ mit fester Initialmarkierung $m\_1(R)$ ist ein schwacher Petri-Netz-Computer (kurz: $m\_1(R)\backslash text\{-\}WPNC$) für eine Funktion $f:\; D\; \backslash to\; \backslash mathbb\{N\}$ ($D\; \backslash subseteq\; \backslash mathbb\{N\}^n$), wenn für alle zulässigen Anfangsmarkierungen $m\_0$ mit $m\_0(R)\; =\; m\_1(R)$, $m\_0(s)\; =\; 1$, $m\_0(o)\; =\; 0$ und $m\_0(X)\; \backslash in\; D$ gilt:

Existiert ein solches $WPNC$ für $f$, dann heißt $f$ WPNC-berechenbar.

Beispiele

WPNC 1 (Addition)

$f(x\_1,\; x\_2)\; =\; x\_1\; +\; x\_2$

Abbildung WPNC 1 (einfacher Addierer ohne innere Stellen)

→ Bild aus dem PDF hier einfügen

WPNC 2 (Multiplikation)

$f(x\_1,\; x\_2)\; =\; x\_1\; \backslash cdot\; x\_2$ mit fester Initialmarkierung $m\_1(R)\; =\; (1,0,0,0)$

Abbildung WPNC 2

→ Bild aus dem PDF hier einfügen

WPNC 3 (Potenzierung)

$f(x)\; =\; x^a$ für festes $a\; \backslash in\; \backslash mathbb\{N\}$ (durch Kaskadierung von Multiplizierern)

Abbildung WPNC 3

→ Bild aus dem PDF hier einfügen

WPNC 4 (Exponentialfunktion)

$f(x)\; =\; 2^x$

Realisiert mit dem Petri-Netz aus Abb. 2 / Abb. 4 (Lemma 4.4). Es gilt stets:

Das Ergebnis wird aus $s\_2$ und $s\_3$ (mit Halbierung) entnommen.

Abbildung WPNC 4

→ Bild aus dem PDF hier einfügen

WPNC 5 (Subtraktion)

$f(x\_1,\; x\_2)\; =\; x\_1\; –\; x\_2$ (für $x\_1\; \backslash ge\; x\_2$)

Abbildung WPNC 5

→ Bild aus dem PDF hier einfügen

WPNC 6 (Modulo-Division)

$f(x)\; =\; x\; \backslash mod\; a$ für festes $a\; \backslash in\; \backslash mathbb\{N\}$

Abbildung WPNC 6

→ Bild aus dem PDF hier einfügen

Weitere Ergebnisse zur WPNC-Berechenbarkeit

• Alle monoton wachsenden Funktionen (inkl. Ackermann-Funktion) sind WPNC-berechenbar.
• Nicht-monotone Funktionen wie Subtraktion, Division und Modulo sind mit gewöhnlichen Petri-Netzen nicht WPNC-berechenbar.
• Mit einer Inhibitor-Kante werden Subtraktion und Modulo-Division berechenbar (WPNC 5 und WPNC 6).
• Die ganzzahlige Division $\backslash lfloor\; x\_1\; /\; x\_2\; \backslash rfloor$ erfordert wahrscheinlich zwei Inhibitor-Kanten.

Es gilt die Inklusionskette:

Zählerautomaten (Counter Automata)

Definition 6.2.

Ein n-Band Zählerautomat $CM^n\; =\; (Q,\; \backslash chi)$ besteht aus einer endlichen Zustandsmenge $Q\; =\; \backslash \{q\_1,\; \backslash dots,\; q\_m\backslash \}$ und einer Übergangsfunktion

mit der Eigenschaft:

Definition 6.3.

Eine Funktion $f\; \backslash in\; \backslash mathcal\{F\}$ ist CM³-berechenbar, wenn es einen 3-Band-Zählerautomaten gibt, der für jede Eingabe $x\; \backslash in\; D$ in endlicher Zeit in einer Konfiguration mit $f(x)$ auf einem der Bänder hält.

Theorem 6.1 (Minsky)

Jede algorithmisch berechenbare Funktion $f\; :\; \backslash mathbb\{N\}\; \backslash to\; \backslash mathbb\{N\}$ ist CM³-berechenbar.

Theorem 6.2 (Barsdin)

Für jede CM²-berechenbare Funktion $f$ existieren Konstanten $\backslash phi,\; \backslash omega\; \backslash in\; \backslash mathbb\{N\}$, sodass gilt:

Korollar 6.3

Es gibt Funktionen aus $\backslash mathcal\{F\}$, die mit zweidimensionalen WPNCs (auch mit Inhibitor-Kanten und kontrollierenden Zuständen) nicht berechenbar sind.

Zusammenfassung

• WPNCs können viele wichtige Funktionen berechnen, scheitern aber bei nicht-monotonen Funktionen ohne Inhibitor-Kanten.
• Eine Inhibitor-Kante erweitert die Klasse deutlich (Subtraktion, Modulo).
• Zählerautomaten sind äquivalent zu single-path Petri-Netzen mit Inhibitor-Kanten und kontrollierenden Zuständen.
• Die Minsky-Barsdin-Theoreme geben untere Schranken für die Kompaktheit von Berechnungsmodellen.

Die Frage nach der minimalen Dimension und der minimalen Anzahl von Inhibitor-Kanten für die Berechnung beliebiger Funktionen aus $\backslash mathcal\{F\}$ bleibt für das nächste Kapitel offen.