Sie sind nicht angemeldet.

absynth

Gründervater

  • »absynth« ist männlich

Beiträge: 666

Registrierungsdatum: 10. Dezember 2001

Wohnort: Hannover

Beruf: M. SC. Informatik

21

Mittwoch, 22. August 2007, 14:56

Zitat

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.
I refuse to submit
To the god you say is kind
I know what's right, and it is time
It's time to fight, and free our minds
http://www.christopher-kunz.de/

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11. Dezember 2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

22

Mittwoch, 22. August 2007, 14:57

Zitat

Original von absynth

Zitat

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.
Naja, wenn im Skript die Aussagen A => B und B => A stehen, dann gilt ja wohl auch A <=> B.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

absynth

Gründervater

  • »absynth« ist männlich

Beiträge: 666

Registrierungsdatum: 10. Dezember 2001

Wohnort: Hannover

Beruf: M. SC. Informatik

23

Mittwoch, 22. August 2007, 14:59

Zitat

Original von JoachimNaja, wenn im Skript die Aussagen A => B und B => A stehen, dann gilt ja wohl auch A <=> B.

Na, manchmal gibts ja fiese Tricks (in diesem Fall z.b., daß die Sätze nur unter verschiedenen Schlußregeln gelten oder sowas), aber wenn dem nicht so ist, dann ist ja alles fein. Zumindest relativ.
I refuse to submit
To the god you say is kind
I know what's right, and it is time
It's time to fight, and free our minds
http://www.christopher-kunz.de/

Mister X

Zuhörer

Beiträge: 2

Registrierungsdatum: 30. September 2007

24

Sonntag, 30. September 2007, 18:31

Hallo, vielleicht hat ja jemand Lust und Zeit und das Verständnis uns ein paar Fragen zu BuL zu beantworten:

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 endscheidbar 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?

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Mister X« (30. September 2007, 18:33)


Arne

ThI

  • »Arne« ist männlich

Beiträge: 1 797

Registrierungsdatum: 7. Oktober 2002

Wohnort: Hannover :)

Beruf: Lecturer ThI

25

Sonntag, 30. September 2007, 19:51

Zitat

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.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11. Dezember 2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

26

Sonntag, 30. September 2007, 20:32

Zitat

Original von Arne

Zitat

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.
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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Mister X

Zuhörer

Beiträge: 2

Registrierungsdatum: 30. September 2007

27

Montag, 1. Oktober 2007, 17:51

Vielen Dank erstmal für die Antworten. So haben wir es uns auch erklärt. Also lagen wir da richtig ;) Wollten nur nochmal sicher gehen.

Hat vielleicht noch jemand ein Antwort für die anderen Fragen parat? Die wären interessanter.

28

Samstag, 6. Oktober 2007, 00:03

Zitat


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?

Bei einer allgemeinen Theorie ist die Rückrichtung nicht unbedingt gegeben. In diesem Fall ist es nicht möglich, aus der Menge der Formeln "F(c)" und "nicht F(c)" die Menge A zu rekonstruieren. Ein Gegenbeispiel konnte ich bisher allerdings nicht konstruieren.

Zitat


2. Ist vollständig = widerspruchsfrei? Gibt es Theorien, die vollständig und widersprüchlich sind?

Theorien sind nach Definition der Vorlesung widerspruchsfrei. Dies schliesst aber bloss die Menge aller Formeln als Theorie aus.

Zitat


3. Können unendliche Mengen entscheidbar sein? z.B. die Menge der natürlichen Zahlen?

Siehe Arnes Antwort.


Zitat


4. Warum führt K arithmetisch auf T* nicht entscheidbar?

Für ein Wort w kann "w in K?" über eine Formel arithmetisch dargestellt werden. Diese Formel ist wahr, wenn das Wort w in K liegt. Wäre die Arithmetik entscheidbar, so könnte man das Halteproblem K über die Arithmetik entscheiden.

Zitat


5. Was bedeutet "Unentscheidbarkeit" der Arithmetik?

Die Arithmetik enthält Mengen von Zahlen, die nicht entscheidbar sind. Man kann also keinen Algorithmus angeben, der für alle Zahlen entscheidet, ob eine Eingabe zu einer Menge gehört, oder nicht.

Zitat


6. Wie zeigt man den Satz von Church (Seite 14) anhand der in Prädikatenlogik verpackten Turingmaschinen?

Es werden eine Formelmenge Gamma und eine Formel D definiert, die die Arbeitsweise einer beliebigen Turing-Maschine M auf einem Wort w kodieren, so dass gilt:
Gamma |-- D gdw. M akzeptiert w

Ein ähnliches Argument wie in der Antwort zu Frage (4.) ergibt dann die Unentscheidbarkeit.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »mtx« (6. Oktober 2007, 12:07)