Diskussion:Cantorsche Paarungsfunktion

Berechnung via Programm

Ich habe eine kleine PHP-Klasse geschrieben, die die Hin- und Rückrechnung ermöglicht. Diese ist in meinen Augen sehr elegant und besteht aus wenigen Zeilen. Wäre es angebracht, auf diese zu verlinken? Oder das Pascal-Code-Beispiel zu ersetzen? Ich könnte sie auch in Java schreiben, falls eine Scriptsprache nicht erwünscht ist.

--Feuervogel 11:19, 2. Feb 2006 (CET)

• Habe nun eine neue Section mit Computerimplementierungen eingefügt. Denke es passt so besser zusammen. --Feuervogel 11:48, 3. Feb 2006 (CET)

Dimension

Auf Wunsch von Benutzer:Marc van Woerkom hier die Begründung, warum ich in der Passage übers kartesische Produkt den Halbsatz "da $M^{2}$ von höherer Dimension als $M$ ist" enfernt habe: Der Dimensionsbegriff ist in der Mathematik beschränkt auf die Charakterisierung von Vektorräumen, projektiven Räumen, Mannigfaltigkeiten, und dergl.. Hinzu kommt noch die Charakterisierung von Fraktalen. Er wird nicht dazu verwandt, allgemein Mengen von n-Tupeln zu charakterisieren. --Juesch 13:42, 6. Sep 2004 (CEST)

So ist es brav. Danke! Dann klappt's auch mit dem Nachbarn. :) --Marc van Woerkom 13:52, 6. Sep 2004 (CEST)

Beweis der Berechenbarkeit

Ich habe noch kein gutes Gefühl dafür, wieviel Detail ein enzyklopädischer Artikel haben soll. Vom Gefühl her würde ich sagen, Definition und Beispiele reichen. Ich würde derzeit die Beweise für die Berechenbarkeit eher wieder rausnehmen. --Marc van Woerkom 04:55, 8. Sep 2004 (CEST)

In der Review wurde moniert, daß der Beweis als offensichtlich angegeben wurde. Daher habe ich ihn eingefügt. Auch wenn er wirklich trivial ist. Das Pacal-Programm habe ich auch wieder eingesetzt, denn es wird zum Beweis der Berechenbarkeit der Umkehrfunktion genutzt. Sonst hätten wir da umstricken müssen.

Das Pascal Programm implementiert die Inverse $\left(\pi \right)^{-1}=(\pi _{1},\pi _{2})$, die ich jetzt explizit als Formel angegeben hatte. Das Programm war mehr eine Gedächtnisstütze, falls ich die Umkehrformel nicht mehr auftreibe. Findest Du nicht, dass die Formeln das Programm ersetzen? Für den Beweís: Sie enthalten ja nur berechenbare Funktionen (Differenz, Verkettung, Maximum suchen..).

Ich find's eigentlich ganz schön, einmal den Beweis über eine Registermaschine zu führen, und einmal über ein While-Programm. Vor allem, wenn das WHILE-Programm in einer umsetzbaren Programmiersprache da steht. Das zeigt sehr deutlich, wie mächtig eigentlich die Definition der Register-Maschinen und die der While-Programme ist. --12:12, 8. Sep 2004 (CEST)

Sind WHILE-Programme nicht Turing-mächtig? --Feuervogel 12:58, 2. Feb 2006 (CET)

Der Beweis für die Gültigkeit der Umkehrformel wäre auch nett, aber dann würden wir ja einen Kursus zur Berechenbarkeitstheorie machen. Wie gesagt, ich habe noch keinen guten Riecher für Ziel und Detailtreue, die hier angestrebt wird. Im Zweifel machen wir, was wir gut finden, und woran die andren wenig mäkeln. :)

--Marc van Woerkom 10:19, 8. Sep 2004 (CEST)

Wenig mäkeln: "Offensichtlich" war denen zu ungenau. Also werden wir genauer. ;-) --TobiasEgg 12:12, 8. Sep 2004 (CEST)

Diskussion aus dem Review

Kopiere mal die Diskussion aus dem Review hierher, dann ist sie näher dran

Hervorragende, verständliche Beschreibung eines mathematischen, komplexen und eigentlich unbegreiflichen Verfahrens, mit einer überabzählbar großen Menge eine scheinbar noch größere Menge abzuzählen. --TobiasEgg 12:02, 6. Sep 2004 (CEST)

Verständlich? Ich verstehe leider nicht mal die Kurzbeschreibung in deinem Vorschlag. Als erste und wichtigste Ergänzung würde ich mir eine etwas umfassendere Einleitung wünschen. Als Vorbild könnten etwa die Ackermann-Funktion oder die Kreiszahl dienen. Vom Omatauglichen zum Fachmathematischen. Liebe Grüße, -- Necrophorus 12:18, 6. Sep 2004 (CEST)

Äh hallo, aber in dem Artikel geht es nur um abzählbare Mengen... Und es gibt deutlich unbegreiflichere Verfahren in der Mathematik. --Berni 12:56, 6. Sep 2004 (CEST)

Dann musst du mich wohl als vollkommen dämlichen Trottel einstufen oder es steht so nicht im Text. Das Wort Menge taucht das erste mal in der Mitte auf, warum nicht in der Einleitung? Nicht falsch verstehe, ich will ncith euern Text kaputtmachen, aber ihr wollt ein Review. Ich als Mathe-Oberlaie verstehe diesen Text nur ansatzweise, also ist er wohl zumindest nicht Necrophorus-tauglich. -- Necrophorus 13:36, 6. Sep 2004 (CEST)

Abgesehen davon, dass Literatur, Hintergrund und innermathematische Anwendungen ganz oder weitgehend fehlen, wird sowas "Die Cantorsche Paarungsfunktion ist offensichtlich berechenbar." wohl ohne weitere Erläuterung so nicht stehenbleiben können. --mmr 12:58, 6. Sep 2004 (CEST)

Die Bererchenbarkeit habe ich mal kurz im Artikel erläutert. Im übrigen finde ich den Artikel auch nicht umwerfend. --Juesch 13:25, 6. Sep 2004 (CEST) Nachtrag: Google zufolge ist der Begriff "Cantorsche Paarungsfunktion" anscheinend im wesentlichen nur im Umfeld eines Prof. Weihrauch an der Fernuni Hagen gebräuchlich. Kennt jemand den "offiziellen" Namen der Funktion? --Juesch 15:35, 6. Sep 2004 (CEST)

Ja, Cantorsche Paarungsfunktion ;-) In anderer Literatur wird sie nicht erläutert, sondern unter den im Artikel beschriebenen Kurzschreibweisen schlicht verwendet bzw. nur mit einem Formelsymbol eingeführt. Siehe z.B.: Erk, Preise, Theoretische Informatik, 2. Auflage, Springer, S. 263 f. und Schöning, Theoretische Informatik kurzgefasst, 4. Auflage, Spektrum, S. 111 f. --TobiasEgg 07:55, 7. Sep 2004 (CEST)

Auch mit ist der Name nicht geläufig, die Funktion tritt in der Cantor-Diagonalisierung auf, wo sie vielleicht auch hingehört. Ich bezweifle of sie einen eigenen Namen hat. Des weiteren ist die gegebene Funktion nichts besonderes, es gibt sicher auch andere Möglichkeiten. Unyxos 23:18, 6. Sep 2004 (CEST)

Die Artikel verweisen aufeinander, das finde ich auch vernünftig - allerdings ist die Cantorsche Paarungsfunktion in der theoretischen Informatik wichtig. Im anderen Beitrag ist sie aus Sicht der Mengenlehre erläutert. Aus Anwendungssicht macht das einen Unterschied. Andere Möglichkeiten der Nummerierung gibt es - die sind aber bis auf Permutation äquivalent. Allerdings gibt es ja auch andere Möglichkeiten, die Zahlen darzustellen usw. (Und auch andere Möglichkeiten, irgendwo nachzuschlagen als in Wikipedia ;-) )

Der Artikel wurde Euren Anmerkungen entsprechend etwas überarbeitet. --TobiasEgg 07:55, 7. Sep 2004 (CEST)

Literatur

Ist es sinnvoll, den FernUni-Kurs als Literatur anzugeben? Der ist schließlich nicht jedem zugänglich. Schlage vor, den durch die Quellen, die ich im Review genannt habe, zu ersetzen. --TobiasEgg 12:18, 8. Sep 2004 (CEST)

Fügst Du die hinzu? --Marc van Woerkom 14:08, 8. Sep 2004 (CEST)

Drin --TobiasEgg 19:28, 8. Sep 2004 (CEST)

Next step

Jetzt sollten wir noch versuchen, das Mathe-DAU-sicher zu machen. So wie das gewünscht wurde. Vielleicht hilft da jemand von den Review-Schreibern. --12:18, 8. Sep 2004 (CEST)

• Ich denke mal, das Hauptproblem dürfte darin liegen, auch einem mathematischen DAU etwas Information zu liefern, worum es sich eigentlich handelt. Ich befürchte, im Moment ist da beim 2. Satz schon Ende der Fahnenstange - da wäre eine omataugliche Zusammenfassung am Anfang sicherlich keine schlechte Idee.
  • Lies mal drüber, ob Du das jetzt besser verstehst. --20:20, 9. Sep 2004 (CEST)~
    • So in der Richtung hatte ich mir das vorgestellt - klingt ganz gut, aber da sollte man dann nochmal bei mathematischen Laien nachfragen. -- srb 21:07, 9. Sep 2004 (CEST)
• Mit den Abschnitten Berechenbarkeit & Anwendung fühle ich mich allerdings auch etwas alleingelassen - klingt irgendwie nach dem Analogon der theoretischen Informatik zum Bronstein ;-) -- srb 19:13, 9. Sep 2004 (CEST)
  • Auch hier überarbeitet - ich weiß ehrlich gesagt nicht mehr, wie ich das noch einfacher machen sollte, ohne komplette andere Artikel hineinzustellen (z.B. die noch zu erstellende Verfeinerung), was IMHO unsinnig wäre. Aber vielleicht hast Du noch Vorschläge. --TobiasEgg 21:54, 9. Sep 2004 (CEST)

Zielsetzung

Ich bin momentan nicht so happy, was aus diesem Artikel geworden ist. Bei mir wäre er viel kürzer und viel mathematischer geworden. Mein Vorbild ist MathWorld von Eric Weisstein. Das wäre dann ein Artikel für Leute, die mathematische Texte verstehen können, was ein gewisses mathematisches Niveau voraussetzt. Wobei man klären müsste, ob das 10. Klasse oder 13. Klasse Schule, oder gar das 3. Semester eines naturwissenschaftlich-technischen Studiums ist.

Ich fürchte, für die Wikipedia ist dass eine Nummer zu hoch. Ist irgendwo mal festgelegt, auf welchem Level man schreiben soll? Oder ist evt. ein Kompromiss möglich? Z.B. allgemeinverständliche Einleitung und dann mathematisch exakter Hauptteil?

Weil die jetztige Mischung finde ich gurkig. Eine Version a la Mathworld würde im wesentlichen aus einem Einleitungssatz und den Definitionen der Paarungsfunktion (2d), ihrer Umkehrung und der Erweiterung auf Tupel bestehen. Ohne zwischendurch zu erklären, was Bijektionen, Mächtigkeit, totale Funktionen, Berechenbarkeit usw. ist. Dafür müssten dann Links reichen.

Wäre eine Serie von Artikeln zu Ideen aus der Theoretischen Informatik, und jetzt spreche ich auch von echter Berechenbarkeitstheorie (was ein paar Nummern heftiger ist, als dies hier) hier überhaupt richtig aufgehoben? Oder müsste man bei einem anderen Projekt, z.B. der Wikiversity oder den Wikibooks eine wissenschaftliche Enzyklopädie für Mathematik/Informatik/Elektrotechnik/Physik anlegen? Also, wo wollen wir bitteschön hin?

Ich habe nichts gegen allgemeinverständliche Artikel, aber zu einfach und damit zu ausführlich ist auch nicht so doll. --Marc van Woerkom 00:39, 10. Sep 2004 (CEST)

Guten Morgen, ich finde es gar nicht soooo schlimm, einen mathematischen Artikel so abzufassen, daß er auch für den Laien ansatzweise nachvollziehbar ist. Manchmal ist es meines Erachtens wichtiger, dem Leser einen Begriff und eine Vorstellung zu verschaffen, als einen korrekten, minimalistischen Formalismus "hinzuklatschen". Mit dem können nur Informatiker und ähnliche etwas anfangen, mit einer bildhaften Vorstellung im Prinzip jeder etwas.

Und das sollte ja auch das Ziel von Wikipedia sein: Jemand schlägt was nach, kann sich darüber informieren und versteht das. Und zwar jeder. Insofern finde ich den "omatauglich"-Ansatz sehr gut, wenn ich auch den Begriff "Oma" in dem Kontext als unhöflich gegenüber den Omas sehe.

Das hier ist ja in dem Sinne keine wissenschaftliche Arbeit (womöglich gar in theoretischer Informatik *grusel*). --TobiasEgg 07:10, 10. Sep 2004 (CEST)

Sollen wir uns nicht mal einen Plan machen, wie wir so einen Artikel aufbauen? Erwarten wir, das der Benutzer alle Links verfolgt, um den Stoff zu kapieren, oder versuchen wir den Artikel eigenständig zu halten (dann wird er wieder sehr lang)? Und Feedback von Nichtmathematiker ist dann sehr wichtig, daher ist die Idee mit den Reviews schon gut. --Marc van Woerkom 11:05, 10. Sep 2004 (CEST)

Ich sehe das so: Läßt sich ein Begriff in einem Nebensatz für die Anschauung vernünftig beschreiben, wie. z.B. "bijektiv" in dem Beitrag, dann machen wir das. Klar. Ist aber der Begriff relativ aufwendig und nicht wirklich sinnvoll beschreibar, dann ist es günstiger zu verweisen. :-) Ein Artikel sollte natürlich für sich verständlich sein - aber wenn einer nicht weiß was bijektiv, Zahlenfunktion usw. ist und auch keine Vorstellung hat: Na ja, wir können hier nicht ein Mathe-Studium verpacken. --TobiasEgg 11:56, 10. Sep 2004 (CEST)

-- Post-Review-Anmerkungen --

Also ich habe nichts gegen leichte Verständlichkeit, so lange die mathematische Exaktheit darunter nicht leidet. Ein Beispielprogramm ist auch gut, wobei eine konkrete Programmiersprache vielleicht ungeeignet ist, da man sich aufgrund der Unterschiede zwischen der "reinen" (also in der Mathematik verwendeten) Arithmetik und der Computerarithmetik schnell Probleme einhandelt. (Rundungsfehler bei Fließkommazahlan, Überläufe bei Ganzzahlen usw.) Siehe auch meine Fragestellung bzw. des Wertebereiches der Cantor-Funktion. Dann könnte man bei dem Programmbeispiel sagen: "Okay, es rechnet auf 32bit-Rechnern bis zur Größe von x=54 oder so richtig, danach kommt es zu Überläufen" oder sowas. --RokerHRO 21:06, 27. Sep 2004 (CEST)

Moment: Die konkrete Programmiersprache Pascal rechnet immer noch theoretisch exakt. Nur ihr reales Compilat auf einem realen Rechner kämpft mit Einschränkungen. Dazu habe ich einen Hinweis eingefügt. --TobiasEgg 14:14, 28. Sep 2004 (CEST)

Neue Review?

Hallo, sollten wir eine neue Review "beantragen"? Ich fänd' schon. --TobiasEgg 07:54, 18. Sep 2004 (CEST)

Andere, einfachere Paarungsfunktionen?

Wäre es sinnvoll/gewünscht/angebracht, hier auch andere Paarungsfunktionen für N×N↏N und ihre Umkehrungen anzugeben? (Da es auch einfachere Paarungsfunktionen gibt, welche vielleicht eher praktisch eingesetzt werden können, da die Werte der Funktion "sparsamer" über N verteilt werden, etwa bei der quadratischen Paarung) --RokerHRO 21:01, 27. Sep 2004 (CEST)

Denke eher nicht, denn andere Funktionen sind nicht die Cantorsche Paarungsfunktion, sondern eben andere Paarungsfunktionen. Abgesehen davon: Sparsamer ist ja eher ein dehnbarer Begriff ;-) --TobiasEgg 21:58, 27. Sep 2004 (CEST)

Das andere Beispiel, was mir einfällt, ist die Möglichkeit über die Primzahlfaktorisierung zu kodieren, z.B.:

$<i,j,k,l,m>=2^{i}3^{j}5^{k}7^{l}11^{m}$

Da die Primzahlzerlegung eindeutig ist, bekommt man auch die Dekodierung wieder hin. --Marc van Woerkom 13:25, 28. Sep 2004 (CEST)

Diese Abbildung ist zwar injektiv, aber Surjektivität und damit Bijektivität lässt sich mit n-Tupeln mit endlichem n nicht erreichen. Ist das dann noch eine "Paarungsfunktion"? --Grünes Ekel (Diskussion) 13:58, 31. Jan. 2018 (CET)

Meiner Meinung nach nicht. Man bekommt daraus eine Bijektion zwischen $\mathbb {N}$ und der Menge der endlichen Folgen natürlicher Zahlen, was sicher auch oft nützlich ist, aber eine Paarungsfunktion ist m.E. eine Bijektion zwischen $\mathbb {N}$ und $\mathbb {N} \times \mathbb {N}$. --Digamma (Diskussion) 20:53, 31. Jan. 2018 (CET)

Wertebereich?

Auch über den Wertebereich könnte man noch etwas schreiben. Sprich, wenn man Zahlen aus dem Intervall [0;n[ in die Cantor-Funktion steckt, in welchem Wertebereich liegen dann die Ergebnisse? Optimal wäre ja [0;(n+1)²-1[ oder sowas in dem Dreh. --RokerHRO 21:01, 27. Sep 2004 (CEST)

Äh, wie???? *aufderleitungsitzend* Ich stecke in die Cantorsche Paarungsfunktion ja mindestens ein 2-Tupel, also allenfalls Zahlen aus der Menge [0;n[ x [0;n[. Dafür läßt sich natürlich eine Obergrenze abschätzen. Ob das Sinn macht? --TobiasEgg 21:59, 27. Sep 2004 (CEST)

Formel für n-Tupel

Es wäre schön, wenn man acuh eine geschlossene Formel für die Abbildung von $N^{n}\to N$ angeben würde, incl. Umkehrfunktion natürlich. --RokerHRO 21:01, 27. Sep 2004 (CEST)

Warum? Ist doch offensichtlich, wie die Rekursion zu berechnen ist. Eine geschlossene Formel ist da dann nur noch eine Fleißaufgabe, die nicht mal mehr im Ergebnis besonders verständlich ist? --TobiasEgg 21:56, 27. Sep 2004 (CEST)

Kandidat für exzellente Artikel

Ich habe, nachdem die Review keine neuen Erkenntnisse mehr gebracht hat, den Status von Review auf Kandidat geändert. Bin gespannt! --TobiasEgg 08:21, 28. Sep 2004 (CEST)

Artikelanfang

Irgendetwas stört mich an dem ersten Satz: "Die cantorsche Paarungsfunktion wird unter diesem Namen in der theoretischen Informatik benutzt." Sollte es nicht eher "Die Cantor-Diagonalisiersung wird unter dem Namen..." heißen, oder "Die cantorsche Paarungsfunktion ist ein Begriff aus der theoretischen Informatik"? Oracle of truth 01:51, 7. Okt 2004 (CEST)

Super, ist jetzt auf jeden Fall besser --Oracle of truth 18:50, 7. Okt 2004 (CEST)

---

Aus Wikipedia:Kandidaten für exzellente Artikel:

Cantorsche Paarungsfunktion, 28. September 2004

aus dem Wikipedia:Review

ohne Wertung, da Mit-Autor. Ich sehe den Artikel mittlerweile als eine gelungene Mischung aus für den Laien verständlich und mathematisch korrekt. So werden beide Leserkreise gut bedient. --TobiasEgg 08:27, 28. Sep 2004 (CEST)

abwartend: [Der Abschnitt Umkehrfunktion scheint mir für einen "Laien" unverständlich. Natürlich kann man nicht alles "omatauglich" beschreiben, doch in diesem Fall würde eine Beispielrechnung das beschriebene für 2-Tupel anschaulicher machen. Zudem ist die Anordnung der Abschnitte merkwürdig: zunächst wird nur vom Fall für 2-Tupel gesprochen. Die Umkehrfunktion bezieht sich dann aber schon auf k-Tupel, bevor diese Verallgemeinerung der Paarungsfunktion überhaupt erwähnt wurde. Auch der Abschnitt Anwendung sollte nach oben verschoben werden.] --Henning.H 10:44, 28. Sep 2004 (CEST)

Ich habe versucht, Deine Anmerkungen umzusetzen - schließlich soll aus "abwartend" noch "pro" werden. --TobiasEgg 13:05, 28. Sep 2004 (CEST)

Das ist weitestgehend gelungen, leider finde ich den Abschnitt Umkehrfunktion immer noch nicht zu 100 % gelungen: vielleicht sollte man hier analog zur Paarungsfunktion vorgehen: erst die Umkehrfunktion für 2-Tupel mit Erläuterung, was "max(v | f(v) <= z)" eigentlich bedeutet, und dem Beispiel, dann die allgemeine Darstellung für n-Tupel. Momentan ist das Beispiel nämlich erst verständlich, wenn man den nachfolgenden Abschnitt "formale Definition" gelesen und verstanden hat, wobei letzteres aufgrund der vorgezogenen (schwierigeren) Definition der Umkehrfunktion für n-Tupel nicht leicht fällt. --Henning.H 19:05, 3. Okt 2004 (CEST)

Ich bin ganz deiner Meinung: erst die formale Definition anzugeben und dann das Beispiel, fände ich auch besser. Lemmie 00:26, 6. Dez 2004 (CET)

• contra: Mathematisch sicher klasse, sogar biologenverständlich. Aber ich finde sowohl den Teil Anwendungen als auch den Teil Herkunft/Geschichte extrem mau dafür, daß der Cantor ja bereits fast 100 Jahre tot ist. Die Funktion hat doch sicher nicht erste Verwendung in der modernen Informatik gefunden, aus irgendeinem Grund muss der Mann die doch entwickelt haben und aus irgendeinem Gruns hat die doch auch bis heute überlebt. Kurz: Nicht nur an die Mathematik denken, auch an Aspekte drumherum. -- Necrophorus 22:26, 29. Sep 2004 (CEST)

Also ganz verstehe ich Deine Kritik jetzt nicht: Cantor hat die Funktion (und das steht da ja auch irgendwo drin) entwickelt, um eine unendliche Menge, nämlich die aller zwei Tupel, mit der Menge der natürlichen Zahlen abzuzählen. Das ist schon ziemlich genial - für sich genommen und reicht leicht aus, um Mathematiker über Jahrzehnte glücklich zu machen. Es schreit daher noch gar nicht mal nach weiterer Anwendung. Daß die theoretische Informatik irgendwann in der Mitte des vorigen Jahrhunderts die Idee dann praktisch nutzen konnte, ist doch toll. Das ist noch längst nicht jeder mathematischen Theorie bisher wiederfahren ;-) --TobiasEgg 15:07, 1. Okt 2004 (CEST)

Ich glaube, du verstehst die Kritik schon: In welcher Form und bei welcher Gelegenheit wurden denn die Mathematiker glücklich gemacht, welche weiteren Theorien und Praktiken konnten sich darauf aufbauend entwickeln, welche Anwendungen außerde der Informatik etc. Mir fehlt einfach etwas Fleich auf den mathematischen Rippe ,siehe dir dazu velleicht mal die Artikel Ackermannfunktion und Scwellwertverfahren an, bei denen das Auffüttern mit etwas Nebeninformation ganz gut gelungen ist.

• absolut pro: Total geiler Artikel, mit dem hab' ich meine Prüfung gerade bestanden. Wenn der dann mal nicht gut ist! --141.76.1.122 17:08, 1. Okt 2004 (CEST)

Auch wenn ich mir heute hier wahrscheinlich keine Freunde machen werde, Contra, aus mehreren Gründen:

• Zum Lemma an sich: Es existiert bereits das Lemma Cantor-Diagonalisierung, in dem im wesentlichen das gleiche Thema behandelt wird. Ich habe arge Zweifel (die ich ziemlich am Anfang im Review geäußert habe), dass "Cantorsche Paarungsfunktion" der "offizielle" Name der Funktion ist, geschweige denn dass es einen solchen überhaupt gibt. Übrigens ist auch das Lemma "Cantor-Diagonalisierung" unglücklich bis falsch. Unter "Cantorschem Diagonalisierungsverfahren" oder "Cantorschem Diagonalargument" oder "Cantor-Diagonalisierung" etc. versteht man m.E. gemeinhin Cantors eleganten Beweis der Überabzählbarkeit der reellen Zahlen (siehe Cantor's diagonal argument in der engl. Wikipedia), nicht den Beweis der Abzählbarkeit von N² oder Q. Man sollte beide Artikel sinnvoll verschmelzen und mit einem neuen, passenden Lemma versehen. Leider fällt mir beim besten Willen kein gescheites ein (Beweis der Abzählbarkeit der Menge der rationalen Zahlen und Implikationen für die Berechenbarkeit von Zahlenfunktionen ist wohl nicht konsensfähig...). Noch mal: ich habe Zweifel, dass das Ding überhaupt einen eigenen Namen hat.

Einspruch ;-):

Ad "Doppellemma": In der Review ist kommentiert, wo der Unterschied zwischen den beiden Lemmata liegt. Ich habe im Review auch einige Literatur genannt, die den Begriff verwendet. Insofern scheint er durchaus existent. --TobiasEgg 08:44, 5. Okt 2004 (CEST)

Zur Namensfrage: Jetzt bin ich aber verwirrt! Dein Kommentar auf meine Anzweiflung des Namens in der Review war: "...In anderer Literatur [außer aus dem Umfeld von Prof. Weihrauch an der Fernuni Hagen] wird sie nicht erläutert, sondern unter den im Artikel beschriebenen Kurzschreibweisen schlicht verwendet bzw. nur mit einem Formelsymbol eingeführt. Siehe z.B..." ("[...]": von mir entsprechend dem Kontext in der Review-Diskussion eingefügt). Ich finde, das kann man nur so verstehen, dass die Funktion in der von Dir im Anschluss dann aufgeführten Literatur (wohl Standard-Lehrbücher) tatsächlich "namenlos" ist. Somit habe ich nach wie vor Zweifel am Lemma, und das wiederum nährt Zweifel an der angeblich so überragenden Bedeutung der Funktion für die theoretische Informatik (Funktionen ohne Namen sind selten wichtig). Was also wolltest Du mit Deinem Statement in der Review nun sagen? Schönen Gruß --Juesch 15:38, 6. Okt 2004 (CEST)

Habe bei Eric Weissteins Mathwold einen Eintrag zu Pairing Function gefunden http://mathworld.wolfram.com/PairingFunction.html, da ist jede Funktion, die ZxZ auf Z zuordnet eine Paarfunktion. Sogar der Begriff Cantors Pairing Function wird verwendet. In dieser Hinsicht sollte der gesamte Artikel vielleicht als Lemma Paarfunktion haben, und die Cantorsche als besonderes Beispiel (weil sie die erste war) detailliert ausgearbeitet werden. Auf jeden Fall sollte aber der Zusammenhang: Cantorsche Paarfunktion ist Spezialfall einer Paarfunktion (und nicht die einzige) dargestellt werden. Unyxos 21:43, 7. Okt 2004 (CEST)

Ad "rationale Zahlen": Die rationalen Zahlen lassen sich als 3-Tupel i,j,k auffassen mit q=(i-j)/(1+k). Mit Cantor gibt es dann eine Zahl z aus N, z = <i,j,k>. Damit kann man auch die rationalen Zahlen abzählen. Das ist aber nur eine (triviale) Anwendung. Für die reellen Zahlen ist eine solche Abzählung nicht möglich - aber das gehört IMHO eher in das Kapitel Abzählbarkeit. --TobiasEgg 08:44, 5. Okt 2004 (CEST)

• Inhaltliches: Ist es nötig, zum Beweis der Berechenbarkeit explizit die Registermachine anzugeben, oder wäre es nicht besser oder "enzyklopädischer", in Worten Die Berechnbarkeit zu begründen? Zur Berechenbarkeit der Umkehrfunktion: Ist das in der Theoretischen Informatik von Bedeutung? - ein bißchen off topic, aber was ich schon immer mal wissen wollte: weiß man eigentlich, ob die Umkehrfunktion einer (injektiven) berechenbaren Funktion immer ebenfalls berechenbar ist, oder gibt's da Ausnahmen? Schönen Gruß --Juesch 18:30, 4. Okt 2004 (CEST)

Ad "Beweis": Der nicht so strenge Beweis wurde im Review kritisiert. Daher hier "sauber" mit einer Registermaschine.

Ich werde den Eindruck nicht los, daß die Registermaschine die Funktion $(x+y)(x+y+1)+y$ berechnet, nicht die gewünschte ${\frac {1}{2}}(x+y)(x+y+1)+y$. -- Gergo 14:41, 6. Okt 2005 (CEST)

Ad "Berechenbarkeit der Umkehrfunktion": Ja, das ist sehr wichtig. Beispiel: f: N² -> N² ist berechenbar, genau dann wenn es gibt ein f' mit f(x,y) = pi^-1(f'(<x,y>)). Da ist es notwendig, bewiesen zu haben, daß pi^-1 berechenbar ist. --TobiasEgg 08:44, 5. Okt 2004 (CEST)

abwartend Zwar ein bisschen spaet, aber besser als nie: Ich finde den Artikel sehr gut. Allerdings zuendet der Funke irgendwie nicht. Und jetzt noch ein paar konstruktive Anmerkungen ;-) Einmal sollte der Artikel graphisch etwas aufgelockert werden. Vielleicht koennte man ein Bild von Cantor spendieren? Stammt das mit der Berechenbarkeit auch schon von Cantor oder wer hat das bewiesen? Schliesslich finde ich den Teil ueber die Umkehrfunktion etwas misslungen: Die Tatsache, dass die Funktion umkehrbar ist, ist ja trivial, schliesslich ist sie ja bijektiv. Wieso also ein so langer Abschnitt der Umkehrfunktion gewidmet wird, kommt fuer mich nicht raus. Viele Gruesse --DaTroll 16:04, 18. Okt 2004 (CEST)

noch nicht

• Das ASCII-Art $\mathbb {N}$ (also das da: |N) finde ich scheußlich und erinnert mich an gruselige PowerPoint-Folien von Informatikern zweifelhafter Professionalität.
• Die cantorsche Paarungsfunktion zeigt jedoch, dass beide Mengen gleich groß sind, denn sie stellt ja eine 1:1 Beziehung her, sie ist eine Bijektion. Hier sollte eindeutig hervorgehoben werden, dass "gleiche Mächtigkeit" genau so definiert ist. Sonst wirkt es sehr wie eine zwar logisch klingende, aber nicht mathematisch präzise Begründung. (Das Standardbeipsiel zur Verdeutlichung: Wenn jmd schreiben würde, $2\mathbb {N}$ ist eine echte Teilmenge von $\mathbb {N}$, so dass die beiden Mengen nicht gleich mächtig sein können, würden es auch alle glauben.) Unter Herkunft wird das Thema dann nochmals angeschnitten, aber wieder nicht präzise zum Ausdruck gebracht, dass es genau die heutige Definition von Gleichmächtigkeit ist. Vielleicht könnte man die beiden halbausgegorenen Anläufe zu einem einzigen, keine Wünsche offen lassenden zusammenfassen.
• Die Sache mit der Primfaktor-Kodierung ist zwar interessant, hat aber sicher nichts im Abschnitt Anwendung verloren.
• Die Literaturliste gibt ein verzerrtes Bild wieder. Reicht denn nicht ein Informatikbuch? Dafür sollte dann aber auch eines aus der Mengenlehre rein.

• Hast Du einen Vorschlag für so ein Buch? --TobiasEgg 10:53, 22. Okt 2004 (CEST)

• Der Fernuni-Hagen-Link stellt in meinen Augen bloße Reklame dar, ich habe nach dem Anklicken nur eine Kursbeschreibung erhalten. Also bitte raus damit.--MKI 12:59, 21. Okt 2004 (CEST)

• Ich hatte noch keine Zeit, die Graphiken in Ruhe ordentlich zu generieren, wollte aber wenigstens die Idee schonmal hier festhalten. Daher ASCII Art. Ein scheussliches Bild sagt hoffentlich immer noch mehr als 1000 Worte.
• Ansonsten ist der Artikel etwas ausgeufert. Ich wollte eigentlich nur Formel und Umkehrformel bringen, weil man das durchaus schon mal praktisch benutzen kann.
• Leider hat der Weihrauch seinen guten Text nicht in einer aktuellen Fassung als Buch gebracht, es gibt nur das mit Schreibmaschine gesetzte Buch. Die FernUni Kurse haben leider auch keine ISBN, sind aber in vielen Städten, z.B. an den Studienzentren einzusehen. Ich habe sogar mal Hagener Kurse in der Physik Fachschaft in Aachen gesehen. Ich würde den Hinweis auf den Kurse gerne beibehalten. Eine ISBN wäre schon besser, dann könnte man das automatische Verlinken in Bibliotheken nutzen.

--Marc van Woerkom 14:44, 21. Okt 2004 (CEST)

Ist das Lemma cantorsche Paarungsfunktion überhaupt gerechtfertigt?

Ich werde den Verdacht nicht los, dass cantorsche Paarungsfunktion gar kein allgemeingebräulicher Begriff ist. Eine Google-Suche liefert jedenfalls nur 45 Treffer, und die liegen alle auf der Wikipedia oder auf Seiten, die die Wikipedia kopiert haben. Ich vermute mal, dass irgendein einzelner Informatiker (vielleicht dieser Weihrauch?) in seinem Buch/Skript diese Funktion, die wohl schon Cantor für den Gleichmächtigkeitsbeweis benutzt hat, vollmundig als cantorsche Paarungsfunktion bezeichnet hat. Wenn wir ehrlich sind, ist die Funktion ja auch gar nichts so besonderes. Ein Erstsemester-Mathestudent würde sofort draufkommen, diese oder eine ähnliche Abbildung für den Beweis zu benutzen. Vielleicht wäre es besser, den Inhalt dieses Artikels in Artikel wie Berechenbarkeit oder Kardinalität einzubauen.--MKI 11:23, 22. Okt 2004 (CEST)

Ich sage, das Lemma ist gerechtfertigt:

Das Argument des Mathe-1.-Semesters kann ich so nicht gelten lassen, schließlich ist auch Kolumbus' Ei letztlich trivial gewesen, man muß aber drauf kommen.

Für den Artikel Berechenbarkeit halte ich das hier für weit zu ausführlich. Diese Ausführlichkeit ist aber, zumindest im Ergebnis der Review, notwendig, um den Beitrag für alle und nicht nur Mathe-Studenten (und Absolventen) verständlich zu machen.

--TobiasEgg 11:30, 22. Okt 2004 (CEST)

Das Argument mit dem Erstsemester sollte nur untermauern, dass die hier behandelte Funktion (weil sie nichts außergewöhnliches ist) wahrscheinlich gar keinen allgemein geläufigen Namen hat. (abgesehen davon: Wenn du die Aufgabe beweise die Gleichmächtigkeit von $\mathbb {N}$ und $\mathbb {N\times N}$ stellst, dann muss das Ei des Kolumbus, sprich die Bijektion, sehr wohl gefunden werden. Und trotzdem ist die Lösung naheliegend.)

Zurück zum Thema: Mir geht es nicht darum, den Inhalt oder die Ausführlichkeit dieses Artikels aus der Wikipedia zu verbannen. Im Gegenteil, ich finde sehr wohl, dass die Information dieses Artikels relevant ist und in der Wikipedia vorhanden sein sollte. Die Frage ist nur, unter welchem Artikel.

Es herrscht nämlich der Konsens darüber, dass die Artikelbezeichnungen (auch Lemmata genannt) nur aus allgemein geläufigen Begriffen oder Namen bestehen sollten. Und diese Voraussetzung scheint mir bei Cantorsche Paarungsfunktion nicht gegeben zu sein.

Ich möchte also bestimmt nicht sabotieren, sondern ein gemeinsames Nachdenken darüber anregen, ob der Inhalt dieses Artikels nicht unter einer anderen Artikelbezeichnung (bzw. evtl. in einem etwas allgemeineren Kontext) besser aufgehoben wäre.--MKI 15:59, 22. Okt 2004 (CEST)

Es geht hier um theoretische Informatik, genauer Berechenbarkeitstheorie - nicht um Mathematik. Prof. Weihrauch ist übrigens ist ein Experte, was die Berechenbare Analysis angeht. Google ist nicht das Mass aller Dinge, schon gar nicht für so Spezialgebiete, die gerade mal einige Diplom- oder Masterstudenten der Informatik interessieren. Noch indiziert Google ja nicht die ganze Fachliteratur. --Marc van Woerkom 22:41, 22. Okt 2004 (CEST)

Cantor war meines Wissens kein Informatiker.

Egal, ob ich Church'sche These, Büchi-Automat, Ackermannfunktion oder while-berechenbar in Google eingebe, stets erhalte ich etliche Vorlesungsskripte verschiedener Personen, in denen diese Stichwörter vorkommen. Bei Cantorsche Paarungsfunktion erscheinen nur Wikipedia & Friends. Aber es stimmt schon, dass Google nicht das optimale Entscheidungskriterium für die Verbreitung eines Wortes ist. Schreibt mir ein paar Bücher hierher, die von Leuten außerhalb des Dunstkreises von Weihrauch verfasst wurden, in denen diese Funktion mit cantorsche Paarungsfunktion benannt wird, und ich nehme alles zurück und behaupte das Gegenteil.--MKI 01:55, 23. Okt 2004 (CEST)

Das Cantor kein Informatik war (bzw. auch sein konnte) ändert nichts daran, daß seine Funktion in der Informatik wichtig ist. Die Berechenbarkeit ist ja auch eine Anwendung der Mathematik :-) --TobiasEgg 12:54, 23. Okt 2004 (CEST)

Vielleicht sollte man das Problem mal anders herum angehen: Wie lautet der englische Fachbegriff für diese Funktion? Spätestens da sollte google doch zumindest ein paar Treffer ausspucken, wenn das Lemma relevant sein sollte - ganz abgesehen davon: gibt es zu diesem Thema wirklich nichts in der en:, auf das man einen iwiki-Link setzen könnte? -- srb 02:20, 23. Okt 2004 (CEST)

Ich hab gesucht und folgendes entdeckt: [1]. Das sieht doch gar nicht schlecht aus. Auch der Aufbau dieses Artikels gefällt mir, da könnte man was übernehmen. Auf englisch scheint die Bezeichnung pairing function also geläufig zu sein, und die natürlichste deutsche Übersetzung ist wohl Paarungsfunktion. Die Frage ist nun: Reicht das als Argument, um Paarungsfunktion als Lemma benutzen zu dürfen? (Anders gefragt: Wäre es rechtens, einen Artikel katalanische Körper für die Duale der archimedischen Körper anzulegen, obwohl mir diese Bezeichnung im Deutschen noch nie begegnet ist, der Artikel auf englisch aber Catalan Solids heißt?)--MKI 11:23, 23. Okt 2004 (CEST)

Paarungsfunktion ist unscharf, da wäre auch die Primfaktor-Paarungsfunktion drin, die ist aber eine andere Paarungsfunktion... --TobiasEgg 12:54, 23. Okt 2004 (CEST)

Eha, beim Nachlesen in Deinem Artikel (Cantor suchen, der zweite Treffer): "This function is known as the Cantor function". Und noch ein Link. --TobiasEgg 12:56, 23. Okt 2004 (CEST)

Sorry, aber das steht da wohl falsch drin. Der Begriff Cantor-Funktion hat eine feste Bedeutung und mit der Paarbildung nichts zu tun: [2]

Ich würde diesen Artikel lieber allgemeiner unter Paarungsfunktion sehen, wenn der Begriff als Lemma passt. Gründe:

• Einerseits trifft vieles, das hier geschrieben wurde, auch auf eine allgemeine Paarungsfunktion zu. Da wäre es doch wünschenswert, dies gleich unter einem allgemeineren Kontext stehen zu haben. Die Änderungen, die dazu vorgenommen müssen, sind minimal und schnell erledigt.
• Die Primfaktor-Paarungsfunktion wäre dann auch so richtig zu Hause, und man könnte gleich noch eine dritte Alternative einfügen, bei der man die Unendlich-Norm Kugeln um (0,0) im $\mathbb {N} ^{2}$ mit steigendem Radius abklappert, genauso wie man es bei der cantorschen Alternative mit den 1-Norm Kugeln tut.
• Ich glaube wirklich nicht, dass der Begriff Cantorsche Paarungsfunktion im Deutschen so richtig gefestigt ist. Wenn man den Artikel schlicht Paarungsfunktion nennt, kann es in dieser Hinsicht nur besser werden.--MKI 14:22, 23. Okt 2004 (CEST)

Mir ist es völlig ein Rätsel, warum hier soviel Aufhebens um einen (ursprünglich kleinen) Artikel gemacht wird, der einfach nur einen netten technischen Kniff aus der Theorie der Berechenbarkeit vorstellen sollte. Tobias war da etwas zu voreilig mit dem promoten. Seufz. Aber was soll's. Ich hatte mir als Publikum Leute gedacht, die sich ein wenig in die Berechenbarkeit einarbeiten wollen, im Zusammenhang mit einem ganzen Haufen noch ungeschriebener Artikel. Da müsste ich eigentlich die Arbeit rein stecken, statt mich hier um Nebensächliches zu streiten. Ich hatte nie die Absicht alle deutschen Matheerstsemester mit diesem Begriff zu impfen. Es ist mir auch voll egal, ob Weihrauch der einzige ist, der dem Ding überhaupt einen Namen gibt. Es ist jedenfalls ein guter Name, inhaltlich ist doch klar worum es geht, oder? Wenn ein Experte wie Weihrauch diesen Begriff gebraucht, sehe ich nicht ein, warum wir hier nicht. Komme mir ja schon fast wie ein Begriffsfälscher vor. Lemma ist jedenfalls überflüssig, da dies einen Hilfssatz bezeichnet und hier wird allenfalls eine Hilfsfunktion vorgestellt. Natürlich springt Dir jeder Artikel hier via Google ins Auge, da Google Referenzen auswertet und x Leute irgendwelche hohlen Wissensportale mit Werbung aufmachen, die als Fleisch Wikipediartikel reinhängen, also findet Google viele Links und setzt das Ergebnis ganz nach vorne. Ansonsten lass uns dochmal abwarten, ob der Peer Review Prozess auch für die Wikipedia funktionieren wird, dazu müssten mal mehr theoretische Informatiker hier vorbei schauen. Das kommt schon. Ich habe die von mir verwendete Literatur gelistet. Wenn Du in der Literatur einen anderen Namen findest, dann her damit. Den Link von Mathworld nehme ich rein. Vermutlich gibt das alte Hopcroft Ullmann Buch (ich habe es am 4.11. wieder in meinem Besitz, aber auch nur auf englisch) dem Ding gar keinen Namen. --Marc van Woerkom 17:13, 23. Okt 2004 (CEST)

Das Wort Lemma hat mehrere Bedeutungen, ich habe es oben auch schonmal angesprochen.

Es ist bei den wenigen Treffern kein Problem, die gesamte Google-Trefferliste durchzusehen. Das habe ich auch gemacht. Ein einziges PDF ist dabei, welches sich mit dem Begriff explizit auf Weihrauch bezieht. Sonst stammt alles über Umwege aus der Wikipedia, auch das, was weiter hinten kommt.

Sollte es so sein, dass nur der Weihrauch den Begriff cantorsche Paarungsfunktion benutzt, dann finde ich es bedenklich, den Artikel unter diesem Lemma enzustellen. Das leitet sich aus dem enzyklopädischen Anspruch ab, den die Wikipedia für sich erhebt.

Ich halte es für sehr normal, dass für einen als exzellent nominierten Artikel Bedenken in der Form geäußert werden, wie ich es hier gemacht habe.

Es wirkt etwas seltsam, nach mehr Mitstreitern zu klagen und gleichzeitig nur widerwillig auf ernstgemeinte Einwände und konstruktive Vorschläge einzugehen. Mich könnt ihr auf alle Fälle gern haben, ich werde mich auf anderen Baustellen umsehen.--MKI 02:56, 25. Okt 2004 (CEST)

Das ist kindisch. Jetzt warte mal ab, da findet sich schon eine Lösung, spätestens wenn ich mal wieder in der Bibliothek war. --Marc van Woerkom 14:42, 25. Okt 2004 (CEST)

Noch "einfacher"

Zur Erklärung meiner Änderungen: Ich habe die Formel 2^x*(2y+1) hinzugefügt, weil sie (ausgehend von einer anderen Idee als der Cantorschen) auch eine Paarungsfunktion liefert, und vielleicht noch einfacher als die Cantorsche Formel ist. Es sollte nicht der Eindruck entstehen, dass die eigentliche Cantorsche Funktion, und ihre trivialen Modifikationen (etwa durch Ändern der Richtung) die einzigen Möglichkeiten sind, Bijektionen zu finden.

Weiters funktioniert die Tupel-Kodierung 2^x*3^y*... nur für positive natürliche Zahlen x,y,.. Für das Prinzip ist das egal, aber der Korrektheit halber sollte das erwähnt werden.

Von "praktisch" im Sinne von "für die Praxis geeignet" kann natürlich keine Rede sein. Praktisch ist diese Kodierung im Sinne der theoretischen Informatik.

-- Wuzel 17:00, 13. Apr 2005 (CEST)

Induktiv?

„Durch mehrfache Anwendung lassen sich auch n-Tupel eindeutig nummerieren. Man definiert induktiv für $k=1,2,3,\ldots$ die Funktionen...“

Kann sein, dass ich mich jetzt irre, aber: ist eine Definition nicht eher „rekursiv“? --FAR 04:08, 9. Sep 2006 (CEST)

Nein, in diesem Falle ist vollständige Induktion gemeint, da von der Gültigkeit für n auf die Gültigkeit von n+1 geschlossen wird.
MikeTheGuru 13:54, 7. Aug. 2007 (CEST)

Berechenbarkeit?

Dass die Paarungsfunktion berechenbar ist, sieht ein Blinder. Jeder Schüler weiß, dass die natürlichen Zahlen und die vier Grundrechenarten berechenbar sind. Sie sind sogar primitiv-rekursiv. Der überflüssige Beweis mit einer Registermaschine dagegen ist ein sicheres Abschreckungsmitttel für alle, die nicht mindestens zwei Semester Berechenbarkeit gehört haben. Woraus folgt übrigens, dass eine bijektive primitiv-rekursive Funktion eine berechenbare Umkehrfunktion hat? Den Beweis dafür würde ich gerne sehen. Der Abschnitt "Umkehrfunktion" sollte vor "Erweiterung auf n-Tupel" kommen. Primitive Rekursivität der Umkehrfunktion wäre auch interessant zu zeigen.--AlfonsGeser 21:57, 11. Jun. 2008 (CEST)

Das mit der Berechenbarkeit der Umkehrfunktion habe ich mittlerweile eingesehen.--AlfonsGeser 22:07, 11. Jun. 2008 (CEST)

Ich stimme zu. Erstens glaube ich nicht, dass wir ein Pascal-Programm brauchen; zweitens aber ist jede durch ein Pascal-Programm berechenbare Funktion berechenbar, also brauchen wir sicher keinen Beweis mit Registermaschinen. Gemeint ist hier natürlich ein ideales Pascal-Programm, in dem der Typ "integer" wirklich alle natürlichen Zahlen als Werte annehmen kann. So ein Programm ist höchstens dann dann sinnvoll, wenn man gerade dabei ist, Übungsbeispiele der Form "beweisen Sie, dass diese Funktion rekursiv ist" zu lösen. Für ein Verständnis der Cantorfunktion trägt dieser Beweis nichts bei.

Weiters gilt, dass die Umkehrfunktion einer berechenbaren totalen (injektiven) Funktion immer berechenbar ist. Also: aus der Berechenbarkeit der Cantorfunktion folgt die Berechenbarkeit der Umkehrfunktion.

Übrigens ist die Umkehrfunktion der Cantorschen Paarungsfunktion natürlich auch primitiv rekursiv, das kann man auf verschiedene Arten beweisen:

1. Die Umkehrfunktion einer streng monotonen prim.rek Funktion $f:\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ ist (auf ihrem Definitionsbereich, dessen charakteristische Funktion prim.rek ist) primitiv rekursiv. (Und die Cantorfunktion ist streng monoton in x und in y.)
2. Die Umkehrfunktion einer primitiv rekursiven Funktion ist sicher dann primitiv rekursiv, wenn sie durch eine primitiv rekursive Funktion beschränkt wird. (Und da für die Cantorfunktion $\pi (x,y)\geq \min(x,y)$ gilt, folgt aus $z=\pi (x,y)$ sicher, dass $x,y$ durch $z$ beschränkt sind.)

--Wuzel 17:57, 6. Aug. 2009 (CEST)

Definition

Die Gleichung ist falsch. Die rechte Seite stimmt, aber die Summenformel ist falsch. $\pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} ,~(x,y)\mapsto \pi (x,y):=\sum _{i=0}^{x+y}i+y={\frac {1}{2}}(x+y)(x+y+1)+y$ (nicht signierter Beitrag von 87.162.29.17 (Diskussion) 14:42, 23. Apr. 2012 (CEST))

Also mein Eindruck ist, dass keine Einigkeit darüber herrscht, ob $\sum _{i=0}^{x+y}i+y$ als $\left(\sum _{i=0}^{x+y}i\right)+y$ oder als $\sum _{i=0}^{x+y}(i+y)$ zu lesen ist. Hier ist jedenfalls ersteres gemeint, und das stimmt dann natürlich. Durch Vertauschen der Summanden kann man das klammerbenutzungsfrei eindeutig machen - und ich mach' das auch gleich mal. --Daniel5Ko (Diskussion) 15:04, 23. Apr. 2012 (CEST)

Codierung mit Primzahlen

Wenn man Tupel mit Hilfe des Fundamentalsatzes der Arithmetik codiert, dann kann man

• entweder: nur positive Einträge zulassen, dann wird das Tutel $\langle i_{1},i_{2},i_{3},i_{4},i_{5},\ldots \rangle$ durch $2^{i_{1}}3^{i_{2}}5^{i_{3}}7^{i_{4}}11^{i_{5}}\cdots$ codiert, zum Beispiel wird das Tripel $\langle 1,3,1\rangle$ durch $2*27*5=270$dargestellt; der größte Primteiler ist 5, die dreitte Primzahl, daraus kann ablesen, dass es sich um ein 3-Tupel handelt.
• oder auch den Eintrag 0 zulassen, dann muss man aber die Exponenten um 1 erhöhen, um den Eintrag 0 von einem nicht vorhandenen Eintrag zu unterscheiden. $\langle i_{1},i_{2},i_{3},i_{4},i_{5},\ldots \rangle$ wird dann durch $2^{i_{1}+1}3^{i_{2}+1}5^{i_{3}+1}7^{i_{4}+1}11^{i_{5}+1}\cdots$ codiert, zum Beispiel wird

• $\langle 1,3,1\rangle$ durch $2^{2}*3^{4}*5^{2}=4*81*25$ dargestellt,
• $\langle 1,3,0\rangle$ durch $2^{2}*3^{4}*5^{1}=4*81*5$,
• $\langle 1,3\rangle$ durch $2^{2}*3^{4}=4*81$.

Wiederum zeigt der größte Teile die Länge des Tupels an.

• Oder man codiert die Länge des Tupels als erste Komponente.

Wuzel (Diskussion) 16:00, 27. Mai 2012 (CEST)

Wenn das analog zu den anderen Tupelkodierungsfunktionen sein soll, ist beim Dekodieren die Länge bereits bekannt und nicht Bestandteil der Daten.

So oder so ist die Kodierung von endlich langen Tupeln über eine Primfaktorzerlegung unschön, da nicht bijektiv. Was man da eigentlich kodiert (in dem Sinn, dass jede Code-Zahl auch einem Datum entspricht), sind unendlich lange Arrays mit jedoch nur endlich vielen Einträgen ungleich 0.

Zum +1: Das wär 'ne zweite Stufe, die man nicht zwangsweise vorgeben muss. Es steht einem ja frei, Null-Einträge als eigentlich gar nicht vorhandene Einträge, und die anderen als beliebige natürliche Zahlen zu interpretieren (1 kodiert eine vorhandene 0, 2 eine vorhandene 1, etc.): $1+\mathbb {N} \cong \mathbb {N}$.

Falls man wirklich beliebig aber endlich lange Listen haben will, mit einer bijektiven Kodierung, dann geht folgendes besser:

• optionale cons-Zellen: $\mathbb {N} ^{*}\cong 1+\mathbb {N} \times \mathbb {N} ^{*}$, oder
• Paare aus Länge und entspr. "Festlängentupel": $\mathbb {N} ^{*}\cong \sum _{n\in \mathbb {N} }\mathbb {N} ^{n}\cong 1+\sum _{n\in \mathbb {N} \setminus \{0\}}\mathbb {N} ^{n}$ (leere Liste wird separat behandelt, um sicherzustellen, dass es für jede Länge, die in einem Paar auftaucht, unendlich viele Tupel gibt; eine Technikalität, die die Kodierung und Dekodierung ein wenig simpler machen dürfte).

--Daniel5Ko (Diskussion) 18:18, 27. Mai 2012 (CEST)