Collatz-Vermutung

Jockelx

Ich denke Spon-Leser sind zwar vielleicht nicht gerade zwingend Bildungselite, aber doch zumindest eher höheres Bildungsniveau.
Und dafür sind die Kommentare teilweise erschreckend dämlich.
Okay, 'angst' ist übertrieben - da war ich noch zu müde.

Jockelx schrieb:

Ich denke Spon-Leser sind zwar vielleicht nicht gerade zwingend Bildungselite, aber doch zumindest eher höheres Bildungsniveau.
Und dafür sind die Kommentare teilweise erschreckend dämlich.
Okay, 'angst' ist übertrieben - da war ich noch zu müde.

Du musst es so sehen: Leute, die die Zeit haben in Internetforen kommentieren, sind nicht gerade die produktivsten Mitglieder der Gesellschaft. Einzige bekannte Ausnahme ist c-plusplus.net/forum.

Erhard Henkes schrieb:

Wie sieht es nun aus? Kann man die Programme zur Berechnung beenden?

Bis zu welcher Zahl bist du schon gekommen ?

Nimm eine beliebige Zahl x und eine weitere Zahl y. Wenn x durch y
teilbar ist, teile x durch y. Wenn nicht, dann bilde das Produkt y
(x+1). Verfahre mit der so jeweils resultierenden neuen Zahl x analog. Nach einer
endlichen Zahl von Schritten landet man bei 1.

jaeljojo schrieb:

Nimm eine beliebige Zahl x und eine weitere Zahl y. Wenn x durch y
teilbar ist, teile x durch y. Wenn nicht, dann bilde das Produkt y
(x+1). Verfahre mit der so jeweils resultierenden neuen Zahl x analog. Nach einer
endlichen Zahl von Schritten landet man bei 1.

für x, y aus N trivial

Gregor schrieb:

AFAIK war Gerhard Opfer ein Schüler von Collatz. Deswegen ist es aus meiner Sicht schon erstaunlich, wenn ein entsprechender Beweis von ihm so schnell widerlegt wird. Ich meine, ich gehe davon aus, dass er sich in dem Bereich wirklich gut auskennt. Gerhard Opfer ist kein Hobbymathematiker, der keine Ahnung hat, was er eigentlich macht. Da erstaunt es, wenn ihm ein derartiger Fehler unterläuft.

Das hier kannte er wohl auch nicht: "The Collatz 3n+1 Conjecture is Unprovable"
--> http://arxiv.org/PS_cache/math/pdf/0312/0312309v19.pdf

SeppJ

Z schrieb:

Das hier kannte er wohl auch nicht: "The Collatz 3n+1 Conjecture is Unprovable"
--> http://arxiv.org/PS_cache/math/pdf/0312/0312309v19.pdf

Es ist schon spät in der Nacht, aber selbst bei kurzem Überfliegen fallen selbst mir als Nicht-Mathematiker da dran Mängel auf. Die Definition von "zufällig" ist ungewöhnlich. Und Satz 2 halte ich für schlichtweg falsch. Gegenbeweis:
Der Beweis, dass alle Zweierpotenzen auf 1 enden ist so trivial, dass er nicht einmal die Mühe Wert ist, hier hin geschrieben zu werden. Trotzdem ist dieser Beweis sehr viel kürzer (in Bits) als eine hinreichend große Zweierpotenz. qed.

Ein weiterer gescheiterter Versuch. Und noch nicht einmal ein guter.

Jester

Ja, das sieht nach großem Quatsch aus. Gerade arxiv sollte man nicht trauen, da kann sich jeder (wirklich jeder) registrieren und irgendwas hochladen. Arxiv ist super, weil man dort schnell Sachen öffentlich machen kann, die erst später auf Konferenzen (und viel später in Zeitschriften) erscheinen. Außerdem hat man dort keine Seitenbeschränkung. Der Nachteil ist halt, dass da auch ne Menge Unsinn hochgeladen wird, deswegen sollte man sich auf jeden Fall auch die Autoren anschaun.

In dem Fall scheint das irgendeine Privatperson zu sein. Das macht zumindest mich schonmal stutzig, weil die meisten korrekten Veröffentlichungen doch eher von angestellten irgendeiner Uni erstellt werden.

Um nochmal etwas sinnvolles zu diesem Thread beizutragen:

http://preprint.math.uni-hamburg.de/public/papers/hbam/hbam2011-09.pdf

Zweite Seite:

Author's note:
The reasoning on p. 11, that "The set of all vertices (2n; l) in all levels will
contain all even numbers 2n >= 6 exactly once." has turned out to be incomplete.
Thus, the statement \that the Collatz conjecture is true" has to be withdrawn,
at least temporarily.
June 17, 2011

Das ist immerhin das angenehme an Mathematikern: Wenn sie einen (mathematischen) Fehler machen, geben sie ihn in der Regel gleich zu

SeppJ schrieb:

Es ist schon spät in der Nacht, aber selbst bei kurzem Überfliegen fallen selbst mir als Nicht-Mathematiker da dran Mängel auf. Die Definition von "zufällig" ist ungewöhnlich.

Ich bin auch Nichtmathematiker, aber diese Zufallsdefinition hat er aus einem Buch über Informationstheorie, nach dem eine Folge von Ereignissen (0,1), die nicht durch einen Algorithmus rekonstruiert werden kann, als zufällig gilt.

SeppJ schrieb:

Und Satz 2 halte ich für schlichtweg falsch. Gegenbeweis:
Der Beweis, dass alle Zweierpotenzen auf 1 enden ist so trivial, dass er nicht einmal die Mühe Wert ist, hier hin geschrieben zu werden. Trotzdem ist dieser Beweis sehr viel kürzer (in Bits) als eine hinreichend große Zweierpotenz. qed.

Du solltest schon weiterlesen.
Er behauptet, dass eine Zweierpotenz, wenn man sie als Zahl rückwärts hinschreibt, niemals eine Fünferpotenz ergeben kann. Das zu beweisen halte ich nicht für trivial.

Zum "Collatz": Wie wärs mit folgendem Ansatz, wenn wir die beide Pfade getrennt betrachten.

Der eine Pfad macht aus einer geraden Zahl eine gerade oder eine ungerade Zahl (n/2). Und zwar durchschnittlich in jedem zweiten Fall, denn 2/2 => ungerade, 4/2 => gerade, 6/2 => ungerade, 8/2 => gerade, usw. Dafür gibt es sicherlich schon einen mathematischen Beweis.

Der andere Pfad macht aus einer ungeraden Zahl immer eine gerade Zahl, denn 3n+1 => gerade, wenn n ungerade. Auch dafür sollte ein Beweis dem geübten Mathematiker kein Kopfzerbrechen bereiten.

Beides zusammangenommen, generiert die Collatz-Funktion durchschnittlich pro Verdreifachung(+1) zwei Halbierungen, da aus einer ungeraden Zahl immer eine gerade folgt (die im nächsten Schritt halbiert wird), aus einer geraden aber nur in jedem zweiten Fall eine ungerade (die dann verdreifacht wird, wobei die +1 bei großen Zahlen vernachlässigbar ist). Demnach "wachsen" die Glieder einer Collatz-Folge durchschnittlich um den Faktor 3/4, was bedeutet, dass die Tendenz des Kleinerwerdens überwiegt. Und das heisst wiederum, dass es keine Collatz-Folge geben kann, die unendlich lang (ob periodisch oder aperiodisch) ist.

War doch gar nicht so schwer. Wo ist mein Fehler?

SeppJ

Z schrieb:

SeppJ schrieb:

Und Satz 2 halte ich für schlichtweg falsch. Gegenbeweis:
Der Beweis, dass alle Zweierpotenzen auf 1 enden ist so trivial, dass er nicht einmal die Mühe Wert ist, hier hin geschrieben zu werden. Trotzdem ist dieser Beweis sehr viel kürzer (in Bits) als eine hinreichend große Zweierpotenz. qed.

Du solltest schon weiterlesen.
Er behauptet, dass eine Zweierpotenz, wenn man sie als Zahl rückwärts hinschreibt, niemals eine Fünferpotenz ergeben kann. Das zu beweisen halte ich nicht für trivial.

Nein, du musst weiterlesen. Ich beziehe mich auf den Satz 2 aus dem Beweis der Nichtbeweisbarkeit der Collatz-Vermutung. Er behauptet um zu zeigen, dass eine Zahl auf 1 endet, müsste man einen Beweis erbringen, der mindestens so lang ist wie die Zahl selbst. Trotzdem könnte ich einen kurzen Beweis bringen, der zeigt, dass jede Zweierpotenz auf unter der Collatzvorschrift auf 1 endet. Und dieser Beweis ist sicherlich kürzer als 2^9783375635657843657865786578436578953165378943657853657856863785638536, welches bewiesenermaßen zu 1 führt.

SeppJ

Z schrieb:

War doch gar nicht so schwer. Wo ist mein Fehler?

Du kannst nicht in einem Beweis, der für jede Zahl gelten soll mit "durchschnittlich" und "Tendenz" argumentieren. Das darfst du nur, wenn du eine Vermutung begründest. Und das hat schon Herr Collatz.

Jester

Bloß weil eine Aussage im Durchschnitt stimmt muß sie ja nicht immer stimmen. Für die zweier-Potenzen ergibt sich ja zum beispiel nur der gerade-fall, warum sollte es nicht was geben wo sich mehr oder weniger abwechselnd der gerade/ungerade-fall ergibt?

und nein, man muß nicht weiterlesen. Satz 2 ist falsch, daran ändert sich auch nichts wenn man danach weiterliest. Er gibt schlicht keinen Grund an, warum man diese Formeln explizit hinschreiben können müßte um die Collatz-Vermutung zu beweisen, er führt es nur fragwürdig auf was anderes zurück, von dem er offensichtlich noch sicherer ist, dass man es hinschreiben müßte um die Vermutung zu beweisen. Das muß man ihm dann ganz glauben.

Bashar

SeppJ schrieb:

Nein, du musst weiterlesen. Ich beziehe mich auf den Satz 2 aus dem Beweis der Nichtbeweisbarkeit der Collatz-Vermutung. Er behauptet um zu zeigen, dass eine Zahl auf 1 endet, müsste man einen Beweis erbringen, der mindestens so lang ist wie die Zahl selbst.

Nö, das steht da nicht. Da steht, dass man die Werte n, T(n), ..., T^(k-1)(n) (mod 2) angeben muss.

Trotzdem könnte ich einen kurzen Beweis bringen, der zeigt, dass jede Zweierpotenz auf unter der Collatzvorschrift auf 1 endet. Und dieser Beweis ist sicherlich kürzer als 2^9783375635657843657865786578436578953165378943657853657856863785638536, welches bewiesenermaßen zu 1 führt.

In dem Beweis zeigst du allgemeingültig, dass (n, T(n), ..., T^(k-1)(n)) nur aus Nullen besteht.

Du liest eine Aussage über die Länge des Beweises da rein, die da nicht drin steht.

SeppJ

Z schrieb:

SeppJ schrieb:

Es ist schon spät in der Nacht, aber selbst bei kurzem Überfliegen fallen selbst mir als Nicht-Mathematiker da dran Mängel auf. Die Definition von "zufällig" ist ungewöhnlich.

Ich bin auch Nichtmathematiker, aber diese Zufallsdefinition hat er aus einem Buch über Informationstheorie, nach dem eine Folge von Ereignissen (0,1), die nicht durch einen Algorithmus rekonstruiert werden kann, als zufällig gilt.

Seine Formulierung ist aber sehr schlecht:

A vector x in {0,1}^k is random if x cannot be specified in
less than k bits in a computer text-file.

So und nun schreibe ich in meine Computerdatei folgende Beschreibung eines Vektors x der Länge k:

Das alphabetisch kleinste x, welches nicht mit weniger als k-Bits beschrieben werden kann.

Und sobald dein k größer ist als die Länge dieser Aussage, bricht alles zusammen. Das ist so ähnlich wie die berühmte Suche nach der kleinsten uninteressanten Zahl. Sobald du mir diese Sequenz/Zahl nennen kannst ist sie selber nicht mehr zufällig/uninteressant.

Und eigentlich braucht man an dieser Stelle gar nicht mehr weiter zu lesen. Aber ich finde Bashars Einwand interessant. War wohl doch schon zu spät in der Nacht. Mal gucken ob ich ein anderes Gegenbeispiel finde, der Satz schreit jedenfalls nur so danach, falsch zu sein, weil er spezifische Beweismethoden voraussetzt bei denen ich gar nicht einsehe, warum diese nötig sein sollten.

edit: Ich schätze der Gegenbeweis, wäre wohl der Beweis der Collatz-Vermutung . Trotzdem schließt er einfach allerlei Beweismethoden einfach aus und gibt keine Gründe dafür, warum. Es gibt Methoden, um unendlich viele Aussagen gleichzeitig zu beweisen und das wird hier völlig ignoriert.

Jester

SeppJ schrieb:

Und eigentlich braucht man an dieser Stelle gar nicht mehr weiter zu lesen.

Naja, vielleicht solltest Du doch mal noch was lesen: http://de.wikipedia.org/wiki/Kolmogorow-Komplexität

Der Knackpunkt ist, dass die Beschreibung algorithmisch sein muß.

SeppJ

Jester schrieb:

SeppJ schrieb:

Und eigentlich braucht man an dieser Stelle gar nicht mehr weiter zu lesen.

Naja, vielleicht solltest Du doch mal noch was lesen: http://de.wikipedia.org/wiki/Kolmogorow-Komplexität

Der Knackpunkt ist, dass die Beschreibung algorithmisch sein muß.

Das sagt er in seinem Beweis aber nicht. Die Informatiker mögen Zufälligkeit so beschreiben (und das ist auch gut so), er benutzt eine andere Definition und sie taugt nichts.