Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Entscheidbarkeit/Aufzählbarkeit (http://www.informatikerboard.de/board/thread.php?threadid=114)
Geschrieben von moe am 28.12.2006 um 15:12:
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.
Geschrieben von Crotaphytus am 29.12.2006 um 01:30:
Und was sind deine Antworten darauf, die du überprüft haben möchtest?
Geschrieben von moe am 03.01.2007 um 15:55:
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
Geschrieben von Tobias am 04.01.2007 um 19:15:
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.
Geschrieben von moe am 05.01.2007 um 18:00:
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?
Forensoftware: Burning Board, entwickelt von WoltLab GmbH