Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Kernkompetenzbereiche Master-Studium (IS, MMK, NVS, SE, Sys, ThI)
Fragen zu Berechenbarkeit und Logik
Wednesday, August 22nd 2007, 2:56pm
Quoted
Original von Joachim
Ja, steht doch so im Skript.
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wednesday, August 22nd 2007, 2:57pm
Naja, wenn im Skript die Aussagen A => B und B => A stehen, dann gilt ja wohl auch A <=> B.
Original von absynth
Original von Joachim
Ja, steht doch so im Skript.
Nanu? Seh ich nicht, ich sehe nur die beiden bereits erwähnten Sätze, die Konklusion aus beiden (zumindest im Kontext von S. 15) nicht.
Wednesday, August 22nd 2007, 2:59pm
Original von JoachimNaja, wenn im Skript die Aussagen A => B und B => A stehen, dann gilt ja wohl auch A <=> B.
Sunday, September 30th 2007, 7:51pm
Original von Mister X
3. Können unendliche Mengen endscheidbar sein? z.B. die Menge der natürlichen Zahlen?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Sunday, September 30th 2007, 8:32pm
Es gibt auch einfachere Beispiele: wie etwa die bereits angesprochene Menge aller natürlichen Zahlen. Sollte nicht schwer sein, einen Algorithmus (eine TM) anzugeben, der diese Menge entscheidet.
Original von Arne
Original von Mister X
3. Können unendliche Mengen endscheidbar sein? z.B. die Menge der natürlichen Zahlen?
Die Menge L = {a^nb^n | n ist eine natürliche Zahl} ist unendlich und entscheidbar, da es einen Kellerautomaten für L gibt.
Saturday, October 6th 2007, 12:03am
1. Kennt jemand ein Beispiel für eine Funktion, die definierbar ist, aber nicht repräsentierbar? Wo genau liegt der genaue Unterschied zwischen Definierbarkeit und Repräsentierbarkeit?
2. Ist vollständig = widerspruchsfrei? Gibt es Theorien, die vollständig und widersprüchlich sind?
3. Können unendliche Mengen entscheidbar sein? z.B. die Menge der natürlichen Zahlen?
4. Warum führt K arithmetisch auf T* nicht entscheidbar?
5. Was bedeutet "Unentscheidbarkeit" der Arithmetik?
6. Wie zeigt man den Satz von Church (Seite 14) anhand der in Prädikatenlogik verpackten Turingmaschinen?
This post has been edited 1 times, last edit by "mtx" (Oct 6th 2007, 12:07pm)
Wollten nur nochmal sicher gehen.
