BuK/IIm10/BuK-Übung04 G2

Wiki-Quelltext dieser Seite.

=Aufzählbarkeit und Entscheidbarkeit=

== Aufgabe ==
Drücken Sie den Beweis des folgenden Satzes mit Racket aus.
Wenn <math>M</math> eine aufzählbar unendliche Menge ist, dann ist <math>M</math> semi-entscheidbar.

== Lösung ==


= Entscheidbarkeit und Aufzählbarkeit =

== Aufgabe ==
Beweisen Sie: Wenn <math>M</math> entscheidbar ist, dann sind <math>M</math> und <math>A^{\ast}\backslash{}M</math> aufzählbar. Illustrieren Sie anschließend mit Racket.

== Lösung ==
Entscheidbarkeit bedeutet, es exisitert eine (totale) charakteristische Funktion <math>\chi_{M_1,M_2}</math>, welche ein Wort <math>w</math> aus <math>M_2</math> als Eingabe erwartet und "1" zurückgibt, falls <math>w \in M_1</math> und "0", falls <math>w \in M_2\backslash{}M_1</math>.

= Semi-Entscheidbarkeit =
== Aufgabe ==
Zeigen Sie auf der Basis der Semi-Entscheidbarkeit, dass wenn <math>M</math> und <math>A^{\ast}\backslash{}M</math> aufzählbar sind, <math>M</math> entscheidbar ist. Repräsentieren Sie den Beweis anschließend mit Racket.
Verwenden Sie die entwickelten Racket-Prozeduren für folgendes Beispiel: <math>A^{\ast}</math> ist die Menge der natürlichen Zahlwörter, <math>M</math> die Menge der Zahlwörter für die geraden Zahlen und <math>A^{\ast}\backslash{}M</math> die Zahlwörter für die ungeraden Zahlen.

== Lösung ==