| Die letzten 5 Beiträge |
| moe |
Sehe ich das richtig das meine anderen Antworten dann richtig sind?
zu 2: Wenn ich das mit der Church-Turiing-These richtig interpretiere, dann ist das Äquivalenzproblem also entscheidbar für Computerprogramme? |
| Tobias |
Zu 2.) Die Church-Turing-These sollte dir hier weiterhelfen.
Zu 4.)
Ich würde sagen ja. Man stelle sich die Menge aller Polynome mit ganzzahligen Koeffizienten als Tupel vor. Ein Polynom n-ten Grades ist dabei ein (n+1)-Tupel.
Du kannst nun alle Polynome aufzählen, indem du ![[latex]\bigcup_{n \in \mathbb{N}} \mathbb{Z}^n[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\bigcup_{n \in \mathbb{N}} \mathbb{Z}^n) aufzählst.
Zu dem Problem der ganzzahligen Lösungen:
Ein Polynom n-ten Grades mit ganzzahligen Koeffizienten hat nur solche ganzzahligen Nullstellen (ich hoffe das ist hier mit "Lösungen" gemeint), die Teiler von dem konstanten Glied sind (Koeffizient bei x^0).
Zu 6.) Nein, das Halteproblem ist nicht Turing-berechenbar , daher auch nicht aufzählbar. |
| moe |
Alle Antworten konnte ich mir nicht herleiten, deswegen frag ich ja.
zu 1. Nein. Begründung: Gödelsche Unvollstänigkeitssätze
zu 2. Das Äquivalenzproblem ist entscheidbar für DEA´s und NEA´2 sowie nicht entscheidbar für LBA´s. --> Wozu zählen den nun Computerprogramme?
zu 3. Nein. Die Menge der wahren Arithmetischen Formeln ist nicht rekursiv aufzählbar, daher auch nicht semi-entscheidbar.
zu 4. k.a.
zu 5. Nein, wegen 3.??
zu 6. Nein, das Halteproblem ist nicht Turing-berechenbar , daher auch aufzählbar.
Ich bitte um Antworten bzw. Berichtigungen. Danke |
| Crotaphytus |
Und was sind deine Antworten darauf, die du überprüft haben möchtest? |
| moe |
Entscheidbarkeit/Aufzählbarkeit
Hi. Ich hab da mal paar Fragen aus ner Übungsklausur und würde gerne mal meine Antworten überprüft haben bzw. die richtigen Antworten erfahren.
1. (B,F) ist ein Beweissystem für die elementare Zahlentheorie. Können mit (B,F) alle (wahren) Sätze der Zahlentheorie bewiesen werden?
2. Ist das Äquivalenzproblem für Computerprogramme entscheidbar?
3. Ist die Menge WA der wahren arithmetischen Formeln positiv semientscheidbar?
4. Können alle Polynome mit ganzzahligen Koeffizienten, die auch eine ganzzahlige Lösung besitzen, aufgezählt werden?
5. Ist die Menge WA der wahren arithmetischen Formeln negativ semientscheidbar?
6. Kann das allgemeine Halteproblem für Turingmaschinen streng monoton aufgezählt werden?
Für Antworten mit Begründung warum es so ist wäre ich sehr dankbar. |
|
|
