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.

<language>Scheme</language>
== 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>.

Das heißt wir können davon ausgehen, dass die Funktion <math>\chi_{M,A^{\ast}}(w)</math> exisitert.

Die Mengen <math>M</math> und <math>A^{\ast}\backslash{}M</math> sind aufzählbar, wenn es die surjektiven, berechenbaren Funktionen <math>f_M: N \mapsto M</math>
und <math>f_{A^{\ast}\backslash{}M}: N \mapsto A^{\ast}\backslash{}M</math> existieren.

Diese Aufzählfunktionen können unter Verwendung von <math>\chi_{M,A^{\ast}}(w)</math> definiert werden. Dafür benötigen wir noch eine Funktion <math>g</math>, welche die Menge <math>A^{\ast}</math> aufzählt.

<code id="4dac2a35c519c">
(define f-m
  (\lambda (i)
    (if (chi? (g i))
      (g i)
      a)))
</code>

<code id="4dac2a35c51ff">
(define f-m2
  (\lambda (i)
    (if (chi? (g i))
      a
      (g i))))
</code>

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