berechenbarkeit von primzahlen (berechenbarkeitsbegriff)
Neue Frage »

14.10.2004, 22:20 flixgott Auf diesen Beitrag antworten »
berechenbarkeit von primzahlen (berechenbarkeitsbegriff)
also ich definiere mir mal folgende funktion von den von den natürlichen zahlen in die natürlichen zahlen: p(n):= die n-te primzahl.
ich weiss ja, dass es keine explizite vorschrift gibt, aber im sinne der berechenbarkeit frage ich mich, ob p prinzipiell berechen oder nicht und warum..

kann mir jemand mal noch ein paar nicht berechenbare funktionen nennen?
14.10.2004, 22:47 going-entertain Auf diesen Beitrag antworten »

Hm, vielleicht die Ziffernfolge von pi?

Auch nicht explizit möglich.(?)
14.10.2004, 22:50 flixgott Auf diesen Beitrag antworten »

hmmm warum eigentlich nicht.. wie ist das dann mit der ziffernfolge von irrationalen wurzeln?
15.10.2004, 19:26 Rechnender Auf diesen Beitrag antworten »

Die n-te Primzahl ist berechenbar, sogar mit einem sehr einfachen Algorithmus:

code: 
1:
2:
3:
4:
5:
6:
7:

k:=0; i:=1;
while k < n do begin
  i:=i+1;
  if istprim(i) then k:=k+1;
end;
return i;


Auch die Ziffernfolge von pi ist berechenbar, in dem Sinne, dass es einen Algorithmus gibt, der bei Eingabe einer natuerlichen Zahl n die n-te Dezimalziffern von pi berechnet.
Dasselbe gilt fuer alle Quadratwurzeln von in diesem Sinne berechenbaren Zahlen.

Allerdings gibt es nicht berechenbare Zahlenfolgen, ganz einfach, weil es ueberabzaehlbar viele Zahlenfolgen, aber nur abzaehlbar viele Algorithmen gibt.

Eine ganze Reihe von Beispielen kann man konstruieren, wenn man sich auf eine bestimmte Algorithmen-Beschreibungssprache festlegt (z.B. eine Programmiersprache) und dann folgende Zahlenfolge definiert:
Sei a_n um 1 groesser als die groesste natuerliche Zahl, die von einem Algorithmus mit hoechstens n Zeichen bei der Eingabe von n darstellbar ist.
Diese Zahlenfolge kann von keinem Algorithmus berechnet werden, denn seine kuerzeste Formulierung in der gewaehlten Sprache hat eine bestimmte Laenge, die wir m nennen. Dann kann nach Wahl der Folge (a_n) der Wert a_m nicht berechnet werden, weil er groesser ist als die groesste Zahl, die von irgendeinem Algorithmus der Laenge m (bei Eingabe der Zahl m) berechnet werden kann.
15.10.2004, 19:43 flixgott Auf diesen Beitrag antworten »

das geht ein bischen in richtung busy beaver funktion.. das hab ich auch schonmal gelesen, wie steht es denn nun noch mit ganz anderen ansätzen?
15.10.2004, 23:16 Rückfragender Auf diesen Beitrag antworten »

Was für Ansätze?
Für nicht berechenbare Folgen oder für Berechnungsvorschriften für berechenbare Folgen?
 Anzeige 
 
16.10.2004, 01:03 lupo1977 Auf diesen Beitrag antworten »

Naja gut, Algorithmen zur Berechnung von Primzahlen gibt es. Allerdings sind diese nicht effizient. Das ist auch das was in vorigen Posts gemeint war. Bis jetzt ist keine schnelle Bildungsvorschrift, welche beliebig grosse Primzahlen erzeugt, bekannt.
16.10.2004, 03:34 going-entertain Auf diesen Beitrag antworten »

Und die Funktion "istprim" müßte dann eine solche uneffiziente sein.
Die Kryptographie lebt ja davon keinen Algorithmus angeben zu können, der den minimalsten Aufwand zur Berechnung von Primfaktoren einer großen Zahl garaniert.
16.10.2004, 11:36 Aiksas78 Auf diesen Beitrag antworten »

Die Funktion istprim kann man doch mit dem Sieb des Erasthostenes implementieren (z.B., es gibt ja auch andere Primzahltests). Natürlich ist das je nach größe der Zahl ein Algorithmus, der keine gute groß 0 Notation verzeichnen kann, aber terminieren wird er schließlich immer...soweit ich den Code verstanden habe wird bei istprim doch nur darauf getestet, dass eine Primzahl vorliegt.
Das bilden einer Primzahl dürfte z.B. mit der Goldbachschen Vermutung ein leichtes sein...
Jedenfalls entspricht das meinem Wissensstand. Korrigiert mich, wenn ich falsch liege.
16.10.2004, 12:25 going-entertain Auf diesen Beitrag antworten »

ah genau, die unklare groß O Notation müsste den Unterschied zu den oben gemeinten "berchenbaren" Funktionen ausmachen.

Bei der busy beaver-Funktion existiert doch ebenfalls kein O(n), oder?
16.10.2004, 12:36 lupo1977 Auf diesen Beitrag antworten »

Die Goldbachse Vermutung besagt das jede gerade Positive Zahl sich als Summe zweier Primzahlen darstellen lässt.

4 = 2+2
6 = 5+1
8 = 3+5
10 = 7+3

und so weiter. Oftmals gibt es sogar mehrere Möglichkeiten.

Beim finden einer Primzahl hilft das nicht wirklich. Wie gesagt alle bekannten Algorithmen scheitern am Ende am Aufwand. Dieser ist zumeist >O(x^{n}) also exponentiell.

Grüsse...
16.10.2004, 13:28 Oudeis Auf diesen Beitrag antworten »

Hallo,

das Finden von Primzahlen ist nicht so schwer, es sind deterministische Primzahltests bekannt, deren Rechenzeit beweisbar nur polynomial mit dem Logarithmus der zu testenden Zahl wächst. Schwierig ist die Faktorisierung hinreichend unauffälliger großer zusammengesetzter Zahlen, die vermutlich nicht in polynomialer Zeit machbar ist. Subexponentielle Algorithmen gibt es aber auch dafür.

Grüße,
Oudeis
16.10.2004, 14:43 lupo1977 Auf diesen Beitrag antworten »

Die Primzahltests liefern aber immer nur mit einer gewissen Wk ob eine Zahl prim ist. Bei grossen Primzahlen muss man hinreichend oft mit diesen Tests iterieren und auch dann kann man nicht sicher sein ob die Zahl tatsächlich prim ist.
Ausserdem ist dann ja immer noch das Problem das dies für sehr viele Zahlen gemacht werden muss. Sprich man wähle eine Zahl zufällig mache den Test sehr oft und hoffe das man nicht eine Zahl erwischt die einem solchen Test lange genug standhält. Immerhin werden Primzahlen ja immer seltener (aber Zahlen die fast Prim sind gibt es viel öfter) auch wenn es unendlich viele gibt.

Zum Beispiel werden auch bei Mersenne Zahlen solche Test angewendet weil man hier zumindest hofft öfters mal eine prime zu erwischen. Aber dennoch dauert dann so ein Nachweis mehrere Jahre. Und am Ende ist sie nur mit einer sehr hohen WK eine Primzahl. Das heisst aber nicht das sie mit WK=1 eine Primzahl ist.


Grüsse...
16.10.2004, 15:15 pimaniac Auf diesen Beitrag antworten »

Das stimmt leider nicht ganz...

Die gängisten Primzahltestalgorithmen geben nur mit einer sehr hohen Wahrscheinlichkeit an ob eine Zahl prim is oder nicht. Die haben den Vorteil dass sie extrem schnell zu rechnen sind, nur manchmal sind sie halt leider falsch.

Auf der anderen Seite gibt es mittlerweile aber auch schon Test bei denen der Aufwand polynomial is, die dir eindeutig bestimmen ob ne ZAhl prim is oder nicht
16.10.2004, 15:59 lupo1977 Auf diesen Beitrag antworten »

Hmm verwirrt solche Algorithmen sind mir nicht bekannt. Wäre nett wenn Du mich da mal informieren könntest. Naja, zugegeben ein Zahlentheoretiker bin ich nicht schon möglich das mir da was nicht bekannt ist. Würde mich schon mal interessieren.

Grüsse...

edit:

Achso bleibt aber immer noch das Problem das für sehr viele Zahlen tun zu müssen.
16.10.2004, 16:43 pimaniac Auf diesen Beitrag antworten »

Ja klar... um die n-te Primzahl auszurechnen gibts natürlich keinen schnellen Algorithmus, weil man immer alle davor ausrechnen muss.
16.10.2004, 21:54 going-entertain Auf diesen Beitrag antworten »

Meinst du damit dass der Rechenschritt um von der (n-1)-ten die n-te Primzahl zu berechnen mit polynomialen Aufwand zu bewältigen ist?
16.10.2004, 23:29 Poff Auf diesen Beitrag antworten »

wie groß war nochmal der Logarithmus von unendlich ... verwirrt
.
17.10.2004, 02:55 going-entertain Auf diesen Beitrag antworten »

Wie meinst du das?
Willst du ausrechnen wie lang es dauert unendlich viele Primzahlen zu berechnen? verwirrt
(bischen) kleiner als nur unendlich smile
21.10.2004, 16:12 flixgott Auf diesen Beitrag antworten »

was ist eigentlich berechenbar und was nicht? wenn ich das richtig verstanden habe, dann gilt doch alles das als berechenbar, was sich in polynomialer laufzeit berechnen läßt(p-probleme) und alles das was sich nicht in polynomialer laufzeit berechnen läßt, als nicht berechenbar (np-probleme).. klärt mich mal verbindlich auf.
dann tauchte im thread auch noch eine frage auf, die mich interessiert:
Zitat:
Bei der busy beaver-Funktion existiert doch ebenfalls kein O(n), oder?
22.10.2004, 00:40 B. Trunken Auf diesen Beitrag antworten »

Berechenbarkeit ist ein Begriff der theoretischen Informatik, der aussagt, ob ein bestimmtes Problem mit einer bestimmten Art von Algorithmen lösbar ist. Je nach Art der Algorithmen gibt es verschiedene Arten von Berechenbarkeit. Mir fallen da folgende, nicht notwendig verschiedene Berechenbarkeitsbegriffe ein:
Turing-berechenbar,
LOOP-berechenbar,
rekursiv,
primitiv-rekursiv.
Es gibt sicherlich weitere.

Die Berechenbarkeit selbst ist nicht direkt an Laufzeitbetrachtungen gekoppelt, d.h. die Bestimmung der n-ten Primzahl ist berechenbar, m.E. sogar LOOP-berechenbar, aber vermutlich nicht polynomiell in log(n).
Ein nicht berechenbares Problem ist selbstverständlich in keiner Zeit, also weder polynomiell noch in anderer Zeit, berechenbar.

Zu fleißigen Bibern kann ich dir leider nichts sagen. Da suchst du vielleicht mal im Netz nach Informationen, oder wartest hier auf welche.
22.10.2004, 11:42 Gast Auf diesen Beitrag antworten »

Zitat:
Original von flixgott
was ist eigentlich berechenbar und was nicht?


Die Ackermann-Funktion ist es nicht:



Die haut JEDEN Stack um!
22.10.2004, 14:13 Oudeis Auf diesen Beitrag antworten »

Zitat:
Original von Gast
Zitat:
Original von flixgott
was ist eigentlich berechenbar und was nicht?


Die Ackermann-Funktion ist es nicht:


Die Ackermannfunktion ist ganz prima berechenbar, denn ihre rekursive Definition lässt sich eins-zu-eins in ein Programm übersetzen, das sie berechnet. Man kann zeigen (durch Induktion über den Aufbau der primitiv-rekursiven Funktionen), daß f(n,n) für jedes primitiv rekursive f asymptotisch langsamer mit n wächst als Ack(n,n), und daraus folgt, daß die Ackermannfunktion nicht primitiv rekursiv ist, aber das ist eine viel schwächere Behauptung als die, die Ackermannfunktion sei nicht berechenbar.
Ein einfaches Beispiel für eine nicht berechenbare Funktion bekommt man beispielsweise, wenn man eine Abzählung der berechenbaren Funktionen von nach wählt und dann betrachtet.

Grüße,
Oudeis
22.10.2004, 14:27 anderer Gast Auf diesen Beitrag antworten »

@Gast:
Auch die rekursiv definierte Additionsfunktion

f(n,0) := n
f(n,m) := f(n,m-1)+1

"haut jeden Stack um".

Lässt du unendliche Stacks zu, passiert auch bei der Ackermann-Funktion nichts dramatisches.
23.10.2004, 06:16 carsten Auf diesen Beitrag antworten »

Ich moechte noch etwas zu den "Primzahltests" ergaenzen.

Es gibt Primzahltests mit denen man bis auf eine selbstgewaehlte Fehlergenauigkeit testen kann, ob eine Zahl eine Primzahl ist oder nicht.

Und es gibt einen (ziemlich neuen) deterministischen Algorithmus (das ist kein Test mehr), mit dem man in polynomieller Zeit eindeutig bestimmen kann, ob eine Zahl prim ist oder nicht.
Link:
http://www.cse.iitk.ac.in/news/primality.html

Gruesse Carsten
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Schulmathematik » Sonstiges » berechenbarkeit von primzahlen (berechenbarkeitsbegriff)