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</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 ==