| Zeige Beiträge 1 bis 3 von 3 Treffern |
|
 Thema: Entscheidbarkeit/Aufzählbarkeit |
|
|
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?
|
|
| Thema: Entscheidbarkeit/Aufzählbarkeit |
|
|
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
|
|
| Thema: 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.
|
|
|
| Zeige Beiträge 1 bis 3 von 3 Treffern |
|
|
|
