Mathe Genie Lexikon Cantorsche Paarungsfunktion Erklärung Bedeutung und Formel

Cantorsche Paarungsfunktion

Die cantorsche Paarungsfunktion wird unter diesem Namen in der theoretischen Informatik benutzt.

Mit ihr kann man ein Paar (i, j) natürlicher Zahlen durch eine einzige natürliche Zahl k darstellen. Man nummeriert damit alle Zahlenpaare. Diese Nummerierung ist sogar eindeutig umkehrbar. Das heißt, man kann aus der Zahl k das ursprüngliche Zahlenpaar (i, j) wieder ermitteln. Die Idee der diagonalen Abzählung von $\mathbb{N}^2$ geht auf Georg Cantor zurück.

Mathematisch gesprochen heißt das: Die cantorsche Paarungsfunktion ist eine bijektive totale Funktion, die jedem 2-Tupel (i, j) natürlicher Zahlen eine natürliche Zahl k zuordnet.

Es ist zunächst kaum vorstellbar, daß es möglich ist, alle beliebigen Kombinationen von zwei Zahlen durch eine Zahl zu verschlüsseln: Die Menge aller Zahlenpaare $\mathbb{N}^2 = \mathbb{N}\times\mathbb{N}$ scheint viel größer zu sein, als die Menge aller Zahlen $\mathbb{N}$ . Die cantorsche Paarungsfunktion zeigt jedoch, daß beide Mengen gleich groß sind, denn sie stellt ja eine 1:1 Beziehung her, sie ist eine Bijektion.

Die Menge der natürlichen Zahlen ist abzählbar unendlich. Eine Menge, die man bijektiv auf die natürlichen Zahlen abbilden kann, nennt man ebenfalls abzählbar unendlich. Somit ist die Menge der Paare natürlicher Zahlen abzählbar unendlich.

Inhaltsverzeichnis

1 Definition

2 Erweiterung auf n-Tupel

3 Anwendung

4 Herkunft

5 Umkehrfunktion

5.1 Einführung
5.2 Beispiel
5.3 Formale Definition
5.4 Pascal-Programm zur Berechnung der Umkehrung

6 Berechenbarkeit

6.1 Beweis Berechenbarkeit der cantorschen Paarungsfunktion
6.2 Beweis Berechenbarkeit der Umkehrfunktion

7 Literatur

Definition

$\pi : \mathbb{N} \times \mathbb{N} \to \mathbb{N} : \pi(x, y) = \sum_{i=0}^{x+y} i + y = \frac{1}{2} (x + y) (x + y + 1) + y$

Kurzschreibweise $< i, j > = ?(i, j) = k$ k kodiert das Paar (i, j)

Hier ist eine Skizze der Diagonal-Abzählung:

   | 0   1   2   3   4    y
 --+----------------------->
 0 | 0   2   5   9  14   .
 1 | 1   4   8  13   .
 2 | 3   7  12   .
 3 | 6  11   .
 4 |10   .
   | .
 x v

Auf den Achsen sind die beiden Werte aufgetragen, wie in einer Entfernungstabelle schlägt man den Wert der cantorschen Paarungsfunktion im Schnittpunkt nach, zum Beispiel $< 1,2 > = 8$ .

Die Nummerierung ist denkbar einfach: Man zählt diagonal mit Null beginnend die Paare ab: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2) usw.

Man kann das obige Bildungsgesetz direkt ablesen, wenn man sich die Summation jeweils über eine Spalte verdeutlicht.

Erweiterung auf n-Tupel

Durch mehrfache Anwendung lassen sich auch n-Tupel eindeutig nummerieren. Man definiert induktiv für $k = 1,2,3,\ldots$ die Funktionen $\pi^{(k)} : \mathbb{N}^k \to \mathbb{N}$ mit Hilfe der Paarungsfunktion $?$ durch:

? (1) (x) = x

und

$\pi^{(n+1)}(x_1, \ldots, x_{n+1}) = \pi(\pi^{(n)}(x_1, \ldots, x_{n}), x_{n+1})$

Die Funktionen $? (k)$ bezeichnet man als cantorsche Tupelfunktionen.

Kurzschreibweise $<x_1, x_2, \ldots, x_n> := \pi^{(n)}(x_1, x_2, \ldots, x_n)$

Anwendung

Durch die cantorsche Paarungsfunktionen kann man alle Funktionen, die mehr als einen Parameter haben, auf Funktionen zurückführen, die nur genau einen Parameter haben. Mit ihr lässt sich also die Berechenbarkeit von k-stelligen Zahlenfunktionen auf die Berechenbarkeit von 1-stelligen Zahlenfunktionen reduzieren.

Dadurch kann sich die theoretische Informatik bei der Untersuchung der Berechenbarkeit von Zahlenfunktionen auf die Untersuchung der Berechenbarkeit von einstelligen Zahlenfunktionen beschränken und weiß, dass die gewonnenen Ergebnisse für alle, also auch für die mehrstelligen Zahlenfunktionen gelten.

Herkunft

Die Idee stammt aus der naiven Mengenlehre, wo Georg Cantor die Idee hatte, die Größe einer Menge (Kardinalität, Mächtigkeit) mit der Größe einer anderen Menge zu vergleichen, indem man versucht, eine 1:1 Abbildung (Bijektion) der Elemente dieser Menge mit den Elementen der anderen Menge zu finden. Das erscheint kompliziert, findet aber seine Berechtigung, wenn es um Mengen mit unendlich vielen Elementen geht.

Mit einer Diagonal-Abzählung, wie oben angedeutet, zeigt man leicht, dass bei einer abzählbaren Menge $M$ das kartesische Produkt $M \times M = M^2 = \{ (m, m) | m \in M \}$ genau so mächtig ist wie $M$ , was vielleicht gegen die Intuition spricht, da hier die Mengen in unterschiedlicher Potenz bzw. die Tupel in verschiedener Länge auftreten.

Umkehrfunktion

Die cantorsche Paarungsfunktion ist umkehrbar.

Einführung

Umkehrbar heißt, man kann aus einer Zahl n auf die beiden Zahlen x und y schließen, für die gilt: $n = ?(x, y)$ . Die Umkehrfunktion setzt sich aus zwei Hilfsfunktionen f und q zusammen. Diese Funktionen werden weiter unten formal definiert.

Beispiel

Welches Zahlenpaar repräsentiert die Zahl 17?

Dazu bestimmt man zunächst eine Zahl j, die die größte Zahl ist, für die gilt $f(j) \le 17$ . Das läßt sich am einfachsten durch Ausprobieren ermitteln. Dabei hilft die Wertetabelle von f(j):

 j      1    2    3    4    5    6 
 f(j)   1    3    6   10   15   21

Damit ergibt sich j zu 5. Dann ist y = 17 - f(j) = 17 - f(5) = 17 - 15 = 2. Und x = j - y = 5 - 2 = 3.

Also ist <2,3> = 17. Das läßt sich einfach anhand der Skizze oben verifizieren.

Formale Definition

Man schreibt ihre Inverse $\left(\pi^{(k)}\right)^{-1}:\mathbb{N} \to \mathbb{N}^k$ komponentenweise als $\pi^{(k)}_i:\mathbb{N} \to \mathbb{N}$ , wobei gilt:

$\pi^{(k)}_i = \mbox{pr}^{(k)}_i \circ \left(\pi^{(k)}\right)^{-1}$

vermöge der Projektion

$\mbox{pr}^{(k)}_i(x_1, \ldots, x_k) = x_i$ ,

welche die i-te Komponente aus einem Tupel der Länge k auswählt. Bei Paaren (der Fall $k = 2$ ) schreibt man kurz $\pi^{(2)}_1 = \pi_1$ und $\pi^{(2)}_2 = \pi_2$ , so dass man die Inverse der Paarungsfunktion als $? - 1 = (? 1,? 2)$ schreiben kann.

Mit den Hilfsfunktionen

$f(w) = \sum_{i=0}^w i = \frac{1}{2}w(w+1)$

und

$q(z) = \max\{v | f(v) \le z\}$

kann man $? 1$ und $? 2$ wie folgt berechnen:

? 2 (z) = z - f (q (z))

und

? 1 (z) = q (z) - ? 2 (z)

Pascal-Programm zur Berechnung der Umkehrung

Das folgende Pascal-Programm berechnet die Umkehrfunktion $? - 1$ :

procedure CantorPair(    I   : Integer;
                     Var X,Y : Integer);
{ Gibt das i-te Paar (X,Y) in Diagonalabzaehlung zurueck }
var
   J : Integer;
  
   function F(Z : Integer) : Integer;
   begin
      F := Z * (Z + 1) div 2  
   end;

   function Q(Z : Integer) : Integer;
   var
      V : Integer;
   begin
      V := 0;
      while F(V) <= Z do
         V := V + 1;
      Q := V - 1
   end;

begin
   J := Q(I);
   Y := I - F(J);
   X := J - Y;
end;

Hinweis: Wird das Pascal-Programm auf realen Rechnern übersetzt, muß es mit den Einschränkungen realer Rechner leben. Das heißt insbesondere, daß Speicherplatzbegrenzungen und Rundungsungenauigkeiten das Ergebnis verfälschen können. Das ist allerdings erst bei sehr großen Werten von z bzw. x und y relevant. Für die Anschauung ist ein Pascal-Programm jedoch verständlicher als eine Registermaschine.

Berechenbarkeit

Die cantorsche Paarungsfunktion ist eine totale, bijektive, berechenbare Funktion. Auch ihre Umkehrung ist berechenbar.

Beweis Berechenbarkeit der cantorschen Paarungsfunktion

Eine Methode, zu beweisen, daß eine Funktion berechenbar ist, ist eine Registermaschine anzugeben, die die Funktion berechnet.

Dieser Maschine muss man im Register R1 den Funktionsparameter x und im Register R2 y übergeben. Man erhält dann im Ausgaberegister R0 den Wert von $?$ an der Stelle (x,y).

Die folgende 2-stellige Maschine berechnet die cantorsche-Paarungsfunktion $\pi(x,y) = \frac{1}{2} (x + y) (x + y + 1) + y$ :

R4 = R1 + R2;
R5 = R1 + R2 + 1;
R4 = R4 * R5;
R0 = R4 + R2;

Auf einen formalen Beweis, dass die Registermaschine tatsächlich die Funktion berechnet, wird verzichtet: Das ist offensichtlich erkennbar, wenn man die Funktionsvorschrift zur Berechnung der Cantorschen Paarungsfunktion mit der Maschine vergleicht.

Diese Registermaschine nutzt jedoch Befehle, die die einfache Registermaschine nicht kennt. Die einfache Registermaschine kennt nur die Operationen R+1, R-1 und den einfachen Test.

Durch Verfeinerung lässt sich diese Registermaschine aber auf eine einfache Registermaschine zurückführen.

Damit gibt es eine Registermaschine, die die cantorsche Paarungsfunktion berechnet. Somit ist die cantorsche Paarungsfunktion berechenbar.

Beweis Berechenbarkeit der Umkehrfunktion

Für den Beweis der Umkehrfunktion bietet es sich an, eine andere Definition der Berechenbarkeit zu nutzen:

Eine Funktion ist berechenbar, genau dann, wenn ein WHILE-Programm existiert, das diese Funktion berechnet.

Das oben angegebene Pascal-Programm läßt sich zu einem WHILE-Programm verfeinern. Also gibt es ein WHILE-Programm, das die Umkehrfunktion berechnet. Somit ist auch die Umkehrung berechenbar.

Literatur

Klaus Weihrauch: Computability, Springer (1987), ISBN 3-540-13721-1
Klaus Weihrauch: Einführung in die Theoretische Informatik A, Kurs 01653 (http://www.informatik.fernuni-hagen.de/studium+lehre/kursbestand/knr1653.html) der FernUniversität in Hagen (die aktualisierte Fassung des 1. Teils des Computability Buches, Bezug z. B. im Rahmen eines Akademiestudiums)
Erk, Priese: Theoretische Informatik, 2. Auflage, Springer, S. 263 f, ISBN 3540426248
Schöning: Theoretische Informatik kurzgefasst, 4. Auflage, Spektrum, S. 111 f, ISBN 3827410991

Dieser Artikel ( Cantorsche Paarungsfunktion ) stammt aus Wikipedia, der freien Enzyklopädie
und steht unter der GNU Free Documentation Licence.