Cantorsche Paarungsfunktion

Die Cantorsche Paarungsfunktion, manchmal auch Nummerierungsfunktion genannt, ist eine unter anderem in der theoretischen Informatik verwendete Abbildung, die auf dem Diagonalargument von Cantor basiert.

Mit ihr kann man ein beliebiges Paar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x,y)} natürlicher Zahlen durch eine einzige natürliche Zahl $n$ darstellen. Man nummeriert damit alle Zahlenpaare. Diese Nummerierung ist sogar eindeutig umkehrbar. Das heißt, man kann aus der Zahl $n$ das ursprüngliche Zahlenpaar $(x,y)$ wieder ermitteln. Mathematisch gesprochen heißt das: Die Cantorsche Paarungsfunktion ist eine bijektive totale Funktion $\pi \colon \mathbb {N} ^{2}\to \mathbb {N}$ .

Die Idee der diagonalen Abzählung der Menge aller Paare natürlicher Zahlen geht auf Georg Cantor zurück. Die Verallgemeinerung der Cantorschen Paarungsfunktion von Paaren auf Tupel wird als Cantorsche Tupelfunktion bezeichnet.

Motivation

In der theoretischen Informatik wird die Cantorsche Paarungsfunktion bzw. Tupelfunktion benutzt, um Funktionen, die mehr als einen Parameter haben, auf Funktionen zurückzuführen, die nur genau einen Parameter haben, was viele Beweise deutlich erleichtert.

Die Zurückführung eines Problems auf ein (eventuell einfacheres) bereits bekanntes Problem ist eine bewährte Beweistechnik, die man als Reduktion bezeichnet.

Mit der Cantorschen Paarungsfunktion bzw. Tupelfunktion lässt sich die Berechenbarkeit von $k$ -stelligen Zahlenfunktionen auf die Berechenbarkeit von einstelligen Zahlenfunktionen reduzieren. Das heißt, man kann sich bei der Untersuchung der Berechenbarkeit von Zahlenfunktionen auf die Untersuchung von Einstelligen beschränken und weiß, dass die gewonnenen Ergebnisse für alle (also auch für die mehrstelligen) Zahlenfunktionen gelten.

Grundsätzliches

Es ist vielleicht nicht unmittelbar einsichtig, dass es möglich ist, alle beliebigen Kombinationen von zwei Zahlen durch eine Zahl zu kodieren: 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}$ .

^
|
. . . . . . . . . . . . .
x x x x x x x x x x x x .
x x x x x x x x x x x x .
x x x x x x x x x x x x .              ~
x-x-x-x-x-x-x-x-x-x-x-x-. -->          =          x-x-x-x-x-x-x-x-x-x-x-x-. -->

 $\mathbb {N} \times \mathbb {N}$  als zweidimensionales Gitter 1234567890123456 $\mathbb {N}$  als Menge von Punkten auf dem Zahlenstrahl

Die Cantorsche Paarungsfunktion zeigt jedoch, dass beide Mengen gleich groß sind, denn sie stellt eine 1:1-Beziehung her. Sie ist eine Bijektion.

Eine Menge, die man bijektiv auf die natürlichen Zahlen abbilden kann, nennt man abzählbar unendlich; insbesondere haben die natürlichen Zahlen selbst diese Eigenschaft. Die Cantorsche Paarungsfunktion zeigt dann, dass auch die Menge der Paare natürlicher Zahlen abzählbar unendlich ist.

Definition

Die Cantorsche Paarungsfunktion definiert man als

\pi \colon \mathbb {N} \times \mathbb {N} \to \mathbb {N}

(x,y)\mapsto \pi (x,y):=y+\sum _{i=0}^{x+y}i=y+{\frac {1}{2}}(x+y)(x+y+1)

,

wobei man die natürlichen Zahlen bei 0 beginnen lässt. (Siehe z. B. DIN-Norm 5473)

Kurzschreibweise:

\langle x,y\rangle =\pi (x,y)=n

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} kodiert das Paar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x,y)}

Hier ist eine Skizze der Diagonal-Abzählung:

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle 1, 2\rangle = 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 k-Tupel

Durch mehrfache Anwendung lassen sich auch $k$ -Tupel eindeutig nummerieren. Man definiert induktiv für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k = 1, 2, 3, \dotsc} die Funktionen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{(k)} \colon \mathbb{N}^k \to \mathbb{N}}

mit Hilfe der Paarungsfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} durch:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{(1)}(x) = x}

und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{(k+1)}(x_1, \dotsc, x_{k+1}) = \pi(\pi^{(k)}(x_1, \dotsc, x_{k}), x_{k+1})}

Die Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{(k)}} bezeichnet man als Cantorsche Tupelfunktionen.

Kurzschreibweise:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle x_1, x_2, \dotsc, x_k\rangle := \pi^{(k)}(x_1, x_2, \dotsc, x_k)}

Umkehrfunktion

Die Cantorsche Paarungsfunktion besitzt als Umkehrfunktion die Dreieckswurzel. Die Umkehrung ist eindeutig und berechenbar. Letzteres ist für die Anwendung in der theoretischen Informatik wichtig, da die Berechenbarkeit der Funktion und der Umkehrfunktion Bedingung ist, um ohne Probleme alle berechenbaren Funktionen durch einstellige Funktionen darzustellen.

Umkehrbar heißt, man kann aus einer Zahl $n$ auf die beiden Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} schließen, für die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(x,y)=n} gilt. Die Umkehrfunktion setzt sich aus zwei Hilfsfunktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} zusammen:

Formale Definition

Man schreibt ihre Inverse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(\pi^{(k)}\right)^{-1} \colon \mathbb{N} \to \mathbb{N}^k} komponentenweise als $\pi _{i}^{(k)}\colon \mathbb {N} \to \mathbb {N}$ , wobei gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{(k)}_i = \operatorname{pr}^{(k)}_i \circ \left(\pi^{(k)}\right)^{-1}}

vermöge der Projektion

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{pr}^{(k)}_i(x_1, \dotsc, x_k) = x_i} ,

welche die $i$ -te Komponente aus einem Tupel der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} auswählt.

Bei Paaren (der Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k = 2} ) schreibt man kurz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{(2)}_1 = \pi_1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{(2)}_2 = \pi_2} , sodass man die Inverse der Paarungsfunktion als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{-1} = (\pi_1,\ \pi_2)} schreiben kann.

Mit den Hilfsfunktionen (Dreieckszahl)

f(w)=\sum _{i=0}^{w}i={\frac {w(w+1)}{2}}

und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(z) = \max\{v \mid f(v) \le z\}}

oder (abgerundete Dreieckswurzel)

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(z) = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor}

kann man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi_1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi_2} wie folgt für $z$ berechnen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi_2(z) = z - f(q(z))}

\pi _{1}(z)=q(z)-\pi _{2}(z)

Beispiel

Welches Zahlenpaar repräsentiert die Zahl 17?

Dazu bestimmt man zunächst die größte natürliche Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} , für die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(w) \le 17} gilt. Das lässt sich entweder durch Ausprobieren ermitteln (dabei hilft die Wertetabelle von $f(w)$ ):

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

oder über die abgerundete Formel der Dreieckswurzel:

q(17)=\left\lfloor {\frac {{\sqrt {8\cdot 17+1}}-1}{2}}\right\rfloor =5

Nun kann man einsetzen:

\pi _{2}(17)=17-f(5)=17-{\frac {5(5+1)}{2}}=17-15=2

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi_1(17)=5-2=3}

Also gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle 3, 2\rangle = 17.} Das lässt sich einfach anhand der Skizze oben verifizieren.

Computerimplementierungen

Implementierung der Berechnungen in Java

Bei großen Werten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z} steigt der Zeitbedarf durch die WHILE-Schleife enorm, daher wurde darauf verzichtet, Schleifen zu verwenden, und stattdessen die Variante mit der Dreieckswurzel implementiert:

  public class Cantor {
    public static long compute(long x, long y) {
      return (x+y)*(x+y+1)/2 + y;
    }
    public static long computeX(long z) {
      long j = (long) Math.floor(Math.sqrt(0.25 + 2*z) - 0.5);
      return j - (z - j*(j+1)/2);
    }
    public static long computeY(long z) {
      long j = (long) Math.floor(Math.sqrt(0.25 + 2*z) - 0.5);
      return z - j*(j+1)/2;
    }
  }

Die Methode compute berechnet die dem übergebenen Zahlenpaar (x y) zugeordnete Zahl, computeX und computeY sind die Umkehrfunktionen von compute.

Pascal-Programm zur Berechnung der Umkehrung

Das folgende Pascal-Programm berechnet die Umkehrfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{-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, muss es mit den Einschränkungen realer Rechner leben. Das heißt, dass bei großen Werten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z} Integer-Überläufe das Ergebnis verfälschen. Für die Anschauung ist ein Pascal-Programm jedoch verständlicher als eine Registermaschine.

Berechenbarkeit

Die Cantorsche Paarungsfunktion ist eine totale, bijektive, berechenbare (sogar primitiv-rekursive) Funktion, daher ist auch ihre Umkehrung berechenbar.

Beweis der Berechenbarkeit der Cantorschen Paarungsfunktion

Eine Methode zu beweisen, dass eine Funktion berechenbar ist, ist, eine Registermaschine anzugeben, welche die Funktion berechnet.

Dieser Maschine muss man im Register Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R1} den Funktionsparameter Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} und im Register Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R2} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} übergeben. Man erhält dann im Ausgaberegister Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R0} den Wert von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} an der Stelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x,y)} .

Die folgende zweistellige Maschine berechnet die Cantorsche Paarungsfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(x,y) = \frac{1}{2} (x + y) (x + y + 1) + y} :

R4 = R1 + R2
R5 = R4 + 1
R4 = R4 * R5
R4 = R4 / 2
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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R+1} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 der Berechenbarkeit der Umkehrfunktion

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

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

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

Anwendung der Berechenbarkeit

Aus der Berechenbarkeit der Cantorsche Paarungsfunktion und ihrer Umkehrung folgt, dass es für die Theorie der Berechenbarkeit ausreichend ist, sich mit einstelligen Funktionen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{N} \to \mathbb{N}} zu befassen. Für Funktionen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{N}^n \to \mathbb{N}^m} folgt die Berechenbarkeit dann durch die Anwendung der Cantorschen Paarungsfunktion und ihrer Umkehrfunktion:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f \colon \mathbb{N}^n \to \mathbb{N}^m} ist berechenbar

genau dann, wenn es eine berechenbare Funktion $g\colon \mathbb {N} \to \mathbb {N}$ gibt mit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \forall n \in \mathbb{N}^n: f(n) := \pi_m^{-1} \left(g\left(\pi_n(n)\right)\right).}

Man kann zum Beispiel zeigen, dass sich alle rationalen Zahlen durch ein geordnetes Tripel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (i,j,k)} natürlicher Zahlen darstellen lassen. Damit kann man die Berechenbarkeit leicht von den natürlichen Zahlen auf die Menge der rationalen Zahlen erweitern.

Herkunft

Die Idee stammt aus der Mengenlehre von Georg Cantor. Er hatte die Idee, die Größe einer Menge (Mächtigkeit, Kardinalität) mit der Größe einer anderen Menge zu vergleichen, indem man versucht, eine 1:1-Abbildung (Bijektion) dieser Menge mit der anderen Menge zu finden. Jedem Element der ersten Menge soll genau ein Element der zweiten Menge zugeordnet werden und umgekehrt. Das erscheint kompliziert, findet aber seine Berechtigung, wenn es um Mengen mit unendlich vielen Elementen geht. Siehe auch Galileis Paradoxon.

Mit einer Diagonal-Abzählung (wie oben angedeutet) zeigt man leicht, dass bei einer abzählbaren Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} das kartesische Produkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M \times M = M^2 = \{ (a, b) \mid a,b \in M \}} gleichmächtig ist zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} , was vielleicht gegen die Intuition spricht, da hier Tupel verschiedener Dimension auftreten.

Alternativen

Für zwei benachbarte Punkte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x, y)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x', y')} auf der Trajektorie der Umkehrfunktion kann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \max(|x - x'|, |y - y'|)} beliebig groß werden, was bei der Anwendung der Abzählung unerwünscht sein kann. Daher betrachtet man auch eine Variante der Cantorschen Abzählung, bei der stets Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \max(|x - x'|, |y - y'|) = 1} gilt und die in diesem Sinn stetig ist. Diese Form wird die boustrophedonische Cantor-Abzählung genannt, da hier der Pfad nicht von der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} -Achse zur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} -Achse springt (wie in der Skizze oben dargestellt), sondern an den Achsen wendet. Sie ist auf OEIS als A319571 beschrieben.

Es gibt viele andere Möglichkeiten, Paare natürlicher Zahlen bijektiv durch eine natürliche Zahl zu kodieren, z. B. kann man mit der Formel $\max(r,c)^{2}+\max(r,c)+(-1)^{1+\max(r,c){\text{ mod }}2}\cdot (r-c)$ spiralförmig abzählen:^[1]

r\c	0	1	2	3	4
0	0	1	8	9	.
1	3	2	7	10	.
2	4	5	6	11	.
3	15	14	13	12	.
4	.	.	.	.	.

Auch die einfache Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^x\cdot(2y+1)} liefert eine Bijektion zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\mathbb N}\times {\mathbb N}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\mathbb N} \setminus \{0\}} :

   | 0   1   2   3   4    y
 --+----------------------->
 0 | 1   3   5   7   .
 1 | 2   6  10  14   .
 2 | 4  12  20  28   .         Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z=2^x\cdot(2y+1)}

 3 | 8  24  40  56   .
 4 | .   .   .   .   .
   |
 x v

Beweis der Umkehrbarkeit: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} ist die größte natürliche Zahl so, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^x} ein Teiler von $z$ ist, also die Anzahl der Faktoren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2} in der Primfaktorzerlegung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z} . Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R=\tfrac{z}{2^x}} . Dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y=\tfrac{R-1}2} .

Die Primfaktorzerlegung gibt eine Möglichkeit an, beliebige endliche Tupel natürlicher Zahlen durch natürliche Zahlen zu kodieren:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle i_1, i_2, i_3, i_4, i_5, \dotsc \rangle = 2^{i_1} 3^{i_2} 5^{i_3} 7^{i_4} 11^{i_5} \dotsb}

Beispiel:

\langle 2,1,0,1,0,0\rangle =2^{2}3^{1}5^{0}7^{1}11^{0}13^{0}=4\cdot 3\cdot 7=84

Literatur

Klaus Weihrauch: Computability. Springer, Berlin u. a. 1987, ISBN 3-540-13721-1 (EATCS monographs on theoretical computer science 9).
Eric W. Weisstein: Pairing Function. In: MathWorld (englisch).
Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung. 2. erweiterte Auflage. Springer, Berlin u. a. 2002, ISBN 3-540-42624-8, S. 263 f. (Springer-Lehrbuch).
Uwe Schöning: Theoretische Informatik – kurzgefasst. 4. Auflage. Korrigierter Nachdruck. Spektrum, Heidelberg u. a. 2003, ISBN 3-8274-1099-1, S. 111 f. (Hochschultaschenbuch).

Einzelnachweise

↑ Christoph Michel: Enumerating a Grid in Spiral Order. In: cmichel.io Blog. 7. September 2016, abgerufen am 7. September 2016 (englisch).

[1] Christoph Michel: Enumerating a Grid in Spiral Order. In: cmichel.io Blog. 7. September 2016, abgerufen am 7. September 2016 (englisch).

[1]

Anonym

Suche

Cantorsche Paarungsfunktion

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis

Motivation

Grundsätzliches

Definition

Erweiterung auf k-Tupel

Umkehrfunktion

Formale Definition

Beispiel

Computerimplementierungen

Implementierung der Berechnungen in Java

Pascal-Programm zur Berechnung der Umkehrung

Berechenbarkeit

Beweis der Berechenbarkeit der Cantorschen Paarungsfunktion

Beweis der Berechenbarkeit der Umkehrfunktion

Anwendung der Berechenbarkeit

Herkunft

Alternativen

Literatur

Einzelnachweise

Navigation

Navigation

Mitmachen

Wikiwerkzeuge

Wikiwerkzeuge

Anonym

Suche

Cantorsche Paarungsfunktion

Motivation

Grundsätzliches

Definition

Erweiterung auf k-Tupel

Umkehrfunktion

Formale Definition

Beispiel

Computerimplementierungen

Implementierung der Berechnungen in Java

Pascal-Programm zur Berechnung der Umkehrung

Berechenbarkeit

Beweis der Berechenbarkeit der Cantorschen Paarungsfunktion

Beweis der Berechenbarkeit der Umkehrfunktion

Anwendung der Berechenbarkeit

Herkunft

Alternativen

Literatur

Einzelnachweise

Navigation

Wikiwerkzeuge

Seitenwerkzeuge

Weitere Projekte

Kategorien