 Entscheidbarkeit von Zahlen.. |
foogi
Jungspund
Dabei seit: 06.01.2007
Beiträge: 19
 |
|
| Entscheidbarkeit von Zahlen.. |
     |
hallo,
wie kann man eigentlich entscheiden, ob nun gerade Zahlen entscheidbar sind oder nicht?
sind sie es? wenn ja warum?
ich dachte man kann nur etwas entscheiden wenn man es auch beweisen kann, aber die Zahlen sind doch unendlich?
und wie sieht es mit Primzahlen aus?
danke
|
|
31.01.2007 15:40 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Eine Menge heißt rekursiv entscheidbar oder einfach entscheidbar, wenn es einen Algorithmus gibt, der nach endlicher Zeit terminiert und entscheidet, ob die Eingabe zur Menge gehört oder nicht. (Wikipedia)
Du musst also nur entscheiden, ob ein vorgegebenes (aber beliebiges) Element zu Menge gehört oder nicht. Sprich hier: Ist die Zahl n gerade oder ungerade.
Den Rest kannst du dir selber denken.
|
|
|
31.01.2007 19:06 |
|
|
foogi
Jungspund
Dabei seit: 06.01.2007
Beiträge: 19
|
|
| Zitat: |
Original von Tobias
Eine Menge heißt rekursiv entscheidbar oder einfach entscheidbar, wenn es einen Algorithmus gibt, der nach endlicher Zeit terminiert und entscheidet, ob die Eingabe zur Menge gehört oder nicht. (Wikipedia)
Du musst also nur entscheiden, ob ein vorgegebenes (aber beliebiges) Element zu Menge gehört oder nicht. Sprich hier: Ist die Zahl n gerade oder ungerade.
Den Rest kannst du dir selber denken. |
ich fragte das, weil mir nciht klar ist, warum die Goldbachsche Vermutung nicht entscheidbar ist. Diese basagt, das jede Zahl größer 4, als Summe zweier Primzahlen dargestellt werden kann. Wieso geht das dann hier niciht, wenn es aber bei den Geraden Zahlen geht?
|
|
|
09.02.2007 12:15 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Wenn du eine Menge definierst:
![[latex]G := \{ n \in \mathbb{N} \; | \; n \text{ gerade ist Summe zweier Primzahlen} \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?G := \{ n \in \mathbb{N} \; | \; n \text{ gerade ist Summe zweier Primzahlen} \})
Dann ist ![[latex]G[/latex]](http://www.matheboard.de/latex2png/latex2png.php?G) natürlich entscheidbar (-> probiere alle Primzahltupel (p,q) p,q<n durch.
Das ist aber nicht die Goldbachsche Vermutung. Für die müssten wir eine Mengengleichheit beweisen:
![[latex]G = \{4, 6, 8, 10, \ldots \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?G = \{4, 6, 8, 10, \ldots \})
Jetzt kannst du dir ja mal überlegen, wie man aus diesem Problem ein Entscheidungsproblem machen sollte.
|
|
|
09.02.2007 14:08 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
| Zitat: |
ich fragte das, weil mir nciht klar ist, warum die Goldbachsche Vermutung nicht entscheidbar ist. Diese basagt, das jede Zahl größer 4, als Summe zweier Primzahlen dargestellt werden kann. Wieso geht das dann hier niciht, wenn es aber bei den Geraden Zahlen geht? |
Du vermischt hier unterschiedliche Begriffe. Die Goldbachsche Vermutung ist einfach eine Behauptung für die bisher weder Beweis noch Gegenbeweis gefunden wurde.
Endscheidbarkeit bezieht sich hier auf Formale Sprachen. Bei einem Satz kann man nicht von Entscheidbarkeit reden.
Gruß,
ED
|
|
|
10.02.2007 17:52 |
|
|
|
