---

Geschrieben von foogi am 31.01.2007 um 15:40:

  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

---

Geschrieben von Tobias am 31.01.2007 um 19:06:

 

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.

---

Geschrieben von foogi am 09.02.2007 um 12:15:

 

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?

---

Geschrieben von Tobias am 09.02.2007 um 14:08:

 

Wenn du eine Menge definierst:



Dann ist 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:



Jetzt kannst du dir ja mal überlegen, wie man aus diesem Problem ein Entscheidungsproblem machen sollte.

---

Geschrieben von ed209 am 10.02.2007 um 17:52:

 

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