| Autor |
Beitrag |
    
dakir
| | Veröffentlicht am Mittwoch, den 13. September, 2000 - 12:05: | 
|
Hallo,
ich habe mal in einem Seminar an der Uni gehört, daß es ein iteratives Polynom in zwei Veränderlichen (glaub ich) gibt, welches genau die Primzahlen liefert. Der Professor konnte uns aber auch nichts genaues darüber sagen.
Weiß irgendjemand von Euch mehr darüber?
Vielen Dank, Daniel |
clemens
| | Veröffentlicht am Donnerstag, den 14. September, 2000 - 00:01: |
|
Hallo, Dakir!
Wir hatten mal was Ähnliches in einer Logik-Vorlesung, da gings um formale Zahlentheorie:
Es gibt sogenannte rekursiv aufzählbare Teilmengen der natürlichen Zahlen, die heißen so, falls ein Programm existiert, das keine Eingabe erfordert und als Output alle elemente der Menge liefert. Die Primzahlen sind logischerweise rek. aufzählbar, weil ich kann ja einfach einen Primzahltester bauen und alle natürlichen Zahlen durchlaufen und jede Primzahl ausgeben.
Nun gibt es einen Satz aus der Theorie von Matijasevic (dieser hat übrigens den entscheidenden Durchbruch bei der Lösung des 10. Hilbert'schen Problems geschafft, bei dem es um diophantische Gleichungen geht), welches besagt, daß jede rekursiv aufzählbare Menge das Bild einer 'polynomial partial function' ist. (Sorry die Vorlesung war auf englisch) Das heißt aber nur, daß es eine Polynomfunktion gibt, die als Bildmenge Zahlen liefern, die entweder negativ sind (und dann erklären wir das Resultat einfach als undefiniert) oder in der gewünschten Menge liegen.
Sprich: Man weiß von der Existenz einer Polynomfunktion, die falls man einen Wert einsetzt entweder eine negative Zahl oder eine Primzahl liefert und - würde man alle natürlichen Zahlen einsetzen - auch die gesamten Primzahlen abdeckt.
Das blöde ist nur, daß dieses Resultat zwar schön in der Theorie ist, aber sonst nicht von Wert. Denn man weiß erstens nur von der Existenz (bisher hat glaube ich keiner so eine Funktion konstruieren können) und zweitens wäre uns dann auch nicht sonderlich geholfen, weil man ja nichts darüber weiß wie praktisch die Funktion ist, könnte ja sein, daß die ersten tausendmillionen werte nur negative Zahlen liefern, die Zahlentheorie ist schließlich geduldig.
Wenn du darüber mehr wissen willst kannst du mir gern mailen.
/Clemens |
|
