Entscheidbarkeit von Zahlen..

Neue Frage »

Auf diesen Beitrag antworten »
foogi 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
 
Auf diesen Beitrag antworten »
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.
Auf diesen Beitrag antworten »
foogi

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?
Auf diesen Beitrag antworten »
Tobias

Wenn du eine Menge definierst:

[latex]G := \{ n \in \mathbb{N} \; | \; n \text{ gerade ist Summe zweier Primzahlen} \}[/latex]

Dann ist [latex]G[/latex] 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]

Jetzt kannst du dir ja mal überlegen, wie man aus diesem Problem ein Entscheidungsproblem machen sollte.
 
Auf diesen Beitrag antworten »
ed209

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
 
Neue Frage »
Antworten »


Verwandte Themen

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