 Entscheidbarkeit/Aufzählbarkeit |
moe
Grünschnabel
Dabei seit: 27.12.2006
Beiträge: 3
 |
|
| 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.
|
|
28.12.2006 15:12 |
|
|
Crotaphytus
Mitglied
Dabei seit: 18.09.2006
Beiträge: 45
|
|
Und was sind deine Antworten darauf, die du überprüft haben möchtest?
__________________
Das ist keine Signatur.
|
|
|
29.12.2006 01:30 |
|
|
moe
Grünschnabel
Dabei seit: 27.12.2006
Beiträge: 3
|
|
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
|
|
|
03.01.2007 15:55 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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.
|
|
|
04.01.2007 19:15 |
|
|
|
