Diskussion:Cantorsche Paarungsfunktion

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)

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)

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"?