Vorlesung 3 Lemke

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Übungsaufgaben Seite 9 1.1 Zeigen, dass M, die Menge aller Wörter aus {a,b}* mit Länge 3, entscheidbar ist 1.2 Zeigen, dass M, die Menge aller Wörter aus {a,b}*, die mit a beginnen, entscheidbar ist 2 Übungsaufgabe Seite 10 3 Übungsaufgaben Seite 15 3.1 Zeigen, dass die Menge der geraden Zahlen eine aufzählbare Menge ist 3.2 Zeigen, dass die Menge der Primzahlen aufzählbar ist 4 Übungsaufgaben Seite 16 4.1 Zeigen, dass jede endliche Menge aufzählbar ist 4.2 Menge der Gitterpunkte 4.2.1 Abbildung der natürlichen Zahlen auf die Gitterpunkte 4.2.2 Ordnungsrelation 4.2.3 Funktion zur Berechnung der Platznummer 5 Übungsaufgaben Seite 20 5.1 Beweis Semientscheidbarkeit Halteproblem 5.1.1 Gegenteilige Aussage 1: Das Halteproblem ist vollständig entscheidbar 5.1.2 Gegenteilige Aussage 2: Das Halteproblem ist gar nicht entscheidbar 5.2 Menge der Quadratzahlen 5.2.1 Aufzählfunktion 5.2.2 Berechenbarkeit begründen 5.2.3 Nachweis der Semi-Entscheidbarkeit 5.2.4 Nachweis der Entscheidbarkeit 5.3 Weisen Sie nach, dass die Menge M aller Wörter aus {a, b}∗ , die mit a beginnen, semi-entscheidbar ist. 6 Übungsaufgabe Seite 23

Übungsaufgaben Seite 9

Zeigen, dass M, die Menge aller Wörter aus {a,b}* mit Länge 3, entscheidbar ist

Wir können folgende berechenbare charakterische Funktion schreiben:

def is_element_of_m1(word): if len(word) == 3: return True else: return False

words = {aaa, ab, aab, a} for word in words: print(is_element_of_m1(word))

ausführen

Zeigen, dass M, die Menge aller Wörter aus {a,b}*, die mit a beginnen, entscheidbar ist

Wir können folgende, berechenbare charakterische Funktion schreiben:

def is_element_of_m2(word): if word[0] == 'a': return True else: return False

Übungsaufgabe Seite 10

Übungsaufgaben Seite 15

Zeigen, dass die Menge der geraden Zahlen eine aufzählbare Menge ist

Wir können für die Menge der geraden Zahlen einen Generator schreiben, mit dem sich die geraden Zahlen aufzählen lassen:

def generate_even_numbers(): n = 2 while True: yield n n += 2

even_numbers = generate_even_numbers() for i in range(20): print(next(even_numbers))

ausführen

Zeigen, dass die Menge der Primzahlen aufzählbar ist

Auch hier können wir folgenden Generator definieren, der immer die nächstgrößere Primzahl generiert:

def is_prime(n): if n == 1: return False elif n == 2: return True for i in range(2, n): if n % i == 0: return False return True def generate_prime_numbers(): n = 2 while True: if is_prime(n): yield n n += 1

prime_numbers = generate_prime_numbers() for i in range(100): print(next(prime_numbers))

ausführen

Übungsaufgaben Seite 16

Zeigen, dass jede endliche Menge aufzählbar ist

Wir können einen Generator schreiben, der eine endliche Menge generiert. Er nimmt als Eingabeargument eine beliebige endliche Menge.

def generate_set(finite_set): for i in finite_set: yield i

for i in generate_set({'apple', 'tree', 'pie'}): print(i)

ausführen

Menge der Gitterpunkte

Abbildung der natürlichen Zahlen auf die Gitterpunkte

Ordnungsrelation

def bigger(a: tuple, b: tuple) -> bool: ''' 2) Ordnungsrelation ''' if a[0] > b[0]: return True elif a[0] == b[0]: if a[1] > b[1]: return True

Funktion zur Berechnung der Platznummer

def index(point: tuple) -> float: ''' 3) Berechnung Platznummer ''' appended = str(point[0]) + '.' + str(point[1]) return float(appended)

Übungsaufgaben Seite 20

Beweis Semientscheidbarkeit Halteproblem

→ Beweis durch Negation des Gegenteils mit Gegenbeispiel

Gegenteilige Aussage 1: Das Halteproblem ist vollständig entscheidbar

Dann müsste es für eine unendlich weiterlaufende Funktion False ausgeben. Das passiert aber nicht, weil die Haltefunktion so lange wartet, bis sie merkt, dass diese Funktion aufhört. Wenn sie nicht aufhört, hört auch die Haltefunktion nicht auf und wird auch nie einen Rückgabewert geben. Daher ist sie nicht vollständig entscheidbar.

Gegenteilige Aussage 2: Das Halteproblem ist gar nicht entscheidbar

Wir können das Halteproblem für endlich laufende Funktionen entscheiden, indem wir einfach auf ihr Ende warten und dann True zurück geben, wenn die Funktion gehalten hat. Also ist das Halteproblem in dem Fall, dass eine Funktion nicht unendlich lange läuft, sondern hält, entscheidbar. Damit ist das Halteproblem auch nicht gar nicht entscheidbar.

→ Da das Halteproblem also weder vollkommen entscheidbar noch vollkommen unentscheidbar ist, muss es semi-entscheidbar sein.

Menge der Quadratzahlen

Aufzählfunktion

def generate_square_numbers(): n = 1 while True: yield n * n n += 1

square_numbers = generate_square_numbers() for i in range(20): print(next(square_numbers))

ausführen

Berechenbarkeit begründen

Die Funktion generate_square_numbers, die die Menge der Quadratzahlen generiert, ist berechenbar, weil sie für jedes n eine Quadratzahl generiert. Es gibt kein n, für das die Multiplikation mit sich selbst scheitern würde.

Nachweis der Semi-Entscheidbarkeit

Die Menge der Quadratzahlen ist semi-entscheidbar, weil man jetzt mit der Generierungsfunktion einfach die Menge der Quadratzahlen generieren könnte, bis man das Wort, für das man entscheiden soll, ob es eine Quadratzahl ist, darin gefunden hat.

Nachweis der Entscheidbarkeit

Die Menge der Quadratzahlen ist sogar entscheidbar. Zum einen, weil die Elemente der Quadratzahlen geordnet aufgelistet werden, sodass man vergleichen kann, ob das gesuchte Wort größer als das aktuell betrachtete Mengenelement ist und damit eine Abbruchbedingung hat. Zum anderen, weil man einfach die Wurzel des Wortes nehmen könnte und wenn das Ergebnis eine ganze Zahl ist, ist das vorliegende Wort eine Quadratzahl.

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

Wir haben zuvor schon gezeigt, dass die Wortfunktion von M berechenbar ist. Damit ist M nicht nur semi-entscheidbar, sondern sogar auch entscheidbar. Da sie entscheidbar ist, ist sie auch semi-entscheidbar.

Übungsaufgabe Seite 23

def generate_even_numbers(): n = 2 while True: yield n n += 2 def generate_odd_numbers(): n = 1 while True: yield n n += 2 def union(generator1, generator2): n = 1 while True: if n % 2 != 0: yield next(generator1) elif n % 2 == 0: yield next(generator2) n += 1

even_generator = generate_even_numbers() odd_generator = generate_odd_numbers() union_generator = union(odd_generator, even_generator) for i in range(30): print(next(union_generator))

ausführen