Sind mathematische Beweise mittels Computeralgorithmen gültig?

...komplette Frage anzeigen

5 Antworten

Dazu ein paar Fallunterscheidungen: 

1. Der von dir vorgeschlagene Weg für bei Aussagen für unendlich viel mögliche Fälle nicht zum Ziel. Ob ich eine Aussage für 5, 500, 50000 oder 5 Fantastozilliarden Fälle ausprobiert habe, hat keinerlei Beweiskraft für den allgemeinen Fall, schon bei 6, 501, 50001 oder 5 Fantastozilliarde + 1 kann gerade der Fall versteckt sein, der meine allgemeine Aussage widerlegt. 

2. Anders sieht es aus, wenn ich unter meinen Testfällen einen einzigen finde, der die Aussage widerlegt - Hauptgewinn, damit habe ich dann den Beweis erbracht, dass die Aussage nicht stimmt. Die Kolleginnen und Kollegen werden sich darauf stürzen, es prüfen und mich auf den Schultern zum Nobelpreis (Ach schade, den gibt's für Mathematiker ja nicht...) tragen. 

3. Eine andere Sache sind Probleme, die sich auf endlich viele Fälle reduzieren lassen. Oft sind das zwar immer noch soooo viele Fälle, dass man sie nicht per Hand durchrechnen lassen kann, der Computer spuckt aber vielleicht nach Jahren das Ergebnis aus, dass die Aussage stimmt. Das ist unter Mathematikern "unbeliebt", weil man sich ja auf die Korrektheit des Computersystems, des Programms, des Compilers etc. verlassen muss. Ein Beispiel für diese Art des Beweisens findet man z. B. beim Vierfarbensatz. Da gibt es zwar theoretisch unendlich viele Fälle, die ließen sich aber auf endlich viele Fälle reduzieren - und dann per Computer beweisen. 

4. Das sind schließlich die Computerbeweise, bei denen das Computerprogramm das logische Schließen nachmacht, also selber logische Aussage nach den Regeln der Logik nachmacht. Das ist ein wichtiges Forschungsfeld - bisher können solche Systeme aber nur sehr einfache Dinge beweisen. Auch dagegen gibt es Einwände, weil man sich wiederum auf Technik verlassen mus. 

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von hypergerd
24.01.2016, 15:43

Sehr gut diese Fallunterscheidung. 

Es fehlt nur unter Punkt 1 der Nutzen, den man aus einer hohen Wahrscheinlichkeit oder aus Obergrenzen ziehen kann.

{Beispiel 

Java.math.BigInteger.nextProbablePrime()

Solange man nicht mit Zahlen über 5000 Stellen arbeitet, funktioniert das schnell & zuverlässig }

1
Kommentar von DepravedGirl
24.01.2016, 16:32

@FataMorgana

Recht herzlichen Dank für deine Antwort !

0

Nein, das gilt nicht als Beweis. :)

Vergleiche das doch mal mit der Goldbachschen Vermutung:

https://de.wikipedia.org/wiki/Goldbachsche_Vermutung

Da kannst du mit einem Algorithmus auch nachweisen, dass diese Vermutung für alle untersuchten geraden Zahl zutrifft, aber daraus kann man noch lange nicht ableiten, dass es IMMER so sein muss.

Es ist kein "Beweis", und schon gar kein hieb- und stichfester. :)

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von DepravedGirl
24.01.2016, 06:29

Recht herzlichen Dank für deine Antwort !

Das habe ich leider schon befürchtet, dass es so ist.

1

Wenn es sich um ein Problem handelt, welches sich zu ende rechnen lässt, also z.B. eine Hypothese die für zahlen zwischen Null und Zehnmilliarden gelten soll, dann kann man einfach alle Werte ausrechnen, und das gilt dann, auch wenn es evtl. eine mathematisch elegantere Lösung gibt.

Generell: Wenn du den Algorithmus schon hast, ist es meistens einfach, diesen in eine mathematische Form zu bringen. Schwieriger ist der Beweis der Korrektheit. Für das Szenario was du geschildert hast, ist wahrscheinlich die vollständige Induktion als Instrument für den Beweis ein guter Anfang.


Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von DepravedGirl
25.01.2016, 04:11

Recht herzlichen Dank für deine Antwort !

0

Ich gehe mal davon aus, dass Du Fall 1 von FataMorgana2010 meinst. Leider häufig.

Wie schon mehrfach in den Kommentaren beschrieben:

Java.math.BigInteger.nextProbablePrime()

trotz dem Wissen, dass es nicht zu 100% stimmt, sehr oft benutzte Funktion.

Weshalb ich jedoch einzeln antworte ist der Punkt der Validierung. Unter

http://www.numberworld.org/y-cruncher/

sind zig Weltrekorde von Konstanten zu finden, wo erst blau (anerkannt) wird, wenn eine 2. Berechnung (Verify) mit einem anderen Algorithmus Übereinstimmungen liefert. Das muss nicht jede Stelle sein, da reicht auch jede Millionste ...

Bei Pi geht das besonders schnell, da man die BBP-Formeln kennt, wo man einzelne HEX-Stellen berechnen kann, ohne die zig Bio. Stellen davor beachten zu müssen.

Von über 100 Algorithmen für Pi sind sehr viele bis heute nicht zu 100% bewiesen!

Wenn Du mehr Angaben zu Deinem Problem lieferst, können wir auch noch konkretere Hinweise liefern...

Ein Hinweis noch: 

Ob ein Algorithmus nun in mathematischer- oder Computer-Sprache "aufgeschrieben" wurde, spielt für den Beweis keine Rolle.

http://www.gerdlamprecht.de/Roemisch_JAVA.htm 

setzt in über 120 Beispielen viele Mathe-Algorithmen {Summen, Iterationen,...} in einfachen Code um )

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von hypergerd
24.01.2016, 16:27

siehe auch https://de.wikipedia.org/wiki/Verifizierung#Informatik

zu Punkt 3 von FataMorgana gibt es leider sehr wenig Fälle, die sich von UNENDLICH auf einen endlichen Wert reduzieren lassen.

Oft reicht aber aus, durch Festlegung eines Mindest-Wertes zu sagen: "Solange man unterhalb von .... bleibt, funktioniert der Algorithmus zu 100%" (entspricht Beweis)

1
Kommentar von DepravedGirl
24.01.2016, 16:33

Recht herzlichen Dank für deine Antwort !

0
Der Computeralgorithmus hat für eine große Anzahl von Eingaben stets die korrekten Ausgaben, also Ergebnisse geliefert.

Ist das ein mathematischer Beweis ?

Nein. Es ist ein Hinweis darauf, daß die Annahme nicht so falsch sein kann. Hatte ich mal, ich nahm an, daß das Verteilungsverfahren nach Hare-Niemeyer die Gaußsche Forderung nach Minimierung der Summe der Quadrate der Abweichung erfüllte. Daß die Verteilungsverfahren d'Hondt sowie Sainte-Laguë/Schepers diese Forderung nicht erfüllen hatte ich vorher per Gegenbeispiel herausgefunden. Ich ließ damals meinen Rechner etwa 3 Tage laufen um etwa 5 Mio. Konstellationen zu überprüfen, es gab keinen Fall, in welchem das Verfahren versagte. Danach griff ich zu Papier und Stift, um dies, etwa auf Niveau 10. Klasse, zu beweisen. Der Beweis gelang mir, einige Jahre später las ich auf Wikipedia einen Beweis, welcher den Körperbegriff benutzte. OK., zwei Beweise mit völlig unterschiedlichen Methoden geführt sichern das Ergebnis ab. :-)

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von DepravedGirl
08.02.2016, 14:56

Recht herzlichen Dank für deine Antwort !

1

Was möchtest Du wissen?