BuK/IIm11/BuK-Übung03

Wiki-Quelltext dieser Seite.

==== Aufgabe 1 <tt>(Felix Nitsche, Stefan Lüttke)</tt> ====
ÜA: Wie viele berechenbare charakteristische Funktionen gibt es?
Hinweis: Potenzmenge unendlicher Mengen

==== Aufgabe 2 <tt>(Jens Heider, Daniel Tasche)</tt> ====
ÜA: Zeigen Sie, dass die beiden Mengen aus den Beispielen
entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für
die jeweilige charakteristische Funktion (ProgrammingWiki).


==== Aufgabe 3 <tt>(Max Wielsch, Raik Bieniek)</tt> ====
ÜA: Zeigen Sie, dass die Menge der geraden Zahlen G eine
aufzählbare Menge ist.

ÜA: Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.

ÜA: Wir wissen, dass A* eine abzählbar unendliche Menge ist.
Zeigen Sie, dass A auch aufzählbar ist. 
Hinweis: Hierzu ist es notwendig ein Aufbauschema für A* zu entwerfen und anschließend eine Prozedur dafür zu implementieren.


==== Aufgabe 4 <tt>(Ingo Körner, Christof Ochmann)</tt> ====
ÜA: Zeigen Sie, dass jede endliche Menge aufzählbar ist.

ÜA: Die Menge G der Gitterpunkte (0, 0),(0, 1), ... einer x-y-Ebene ist aufzählbar.

1 Geben Sie eine Funktion f an, die $\N_0$ bijektiv auf G abbildet.

2 Definieren Sie eine Ordnungsrelation $p_<$ in G.

3 Geben Sie eine Funktion k zur Berechnung der Platznummer k(x, y) des betrachteten Gitterpunktes (x, y) an.

4 Geben Sie eine Aufzählprozedur für G an und begründen Sie deren Berechenbarkeit.


==== Aufgabe 5 <tt>(Tobias Salzmann, Ronald Krause)</tt> ====
ÜA: Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese
Aussage.

ÜA: Geben Sie fur die Menge FIBS der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit.
Weisen Sie nach, dass FIBS eine semi-entscheidbare Menge ist.
Zeigen Sie, dass FIBS sogar entscheidbar ist.

ÜA: Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2 |n \in \N\}.$

ÜA: Weisen Sie nach, dass die Menge M aller "Wörter aus {a, b}*, die mit a beginnen, semi-entscheidbar ist.

==== Aufgabe 6 <tt>(Robert Rosenberger, Stefan Scheumann)</tt> ====
ÜA: Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki die 30 ersten Elemente der Vereinigungsmenge (in aufsteigender Sortierung) auszugeben.