BuK/IIm20/Vorlesung 3 Lemke

Wiki-Quelltext dieser Seite.

<language>Python</language>
== Ü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:

<code id="60707b3d8c79c">
def is_element_of_m1(word):
	if len(word) == 3:
		return True
	else:
		return False
</code>
<run id="60707b3d8cb85">
words = {aaa, ab, aab, a}
for word in words:
	print(is_element_of_m1(word))
</run>

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

<code id="60707b3d8c81a">
def is_element_of_m2(word):
	if word[0] == 'a':
		return True
	else:
		return False
</code>

== Übungsaufgabe Seite 10 ==

[[Bild:Anzahlberchebarecharakteristischefunktionen.jpg]]

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

<code id="60707b3d8c897">
def generate_even_numbers():
	n = 2
	while True:
		yield n
		n += 2
</code>
<run id="60707b3d8cbed">
even_numbers = generate_even_numbers()
for i in range(20):
	print(next(even_numbers))
</run>

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

<code id="60707b3d8c8fe">
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
</code>
<run id="60707b3d8cc54">
prime_numbers = generate_prime_numbers()
for i in range(100):
	print(next(prime_numbers))
</run>

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

<code id="60707b3d8c960">
def generate_set(finite_set):
	for i in finite_set:
		yield i
</code>
<run id="60707b3d8ccb9">
for i in generate_set({'apple', 'tree', 'pie'}):
	print(i)
</run>

=== Menge der Gitterpunkte ===

==== Abbildung der natürlichen Zahlen auf die Gitterpunkte ====

[[Bild:Gitterpunkte.jpg]]

==== Ordnungsrelation ====

<code id="60707b3d8c9c0">
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
</code>

==== Funktion zur Berechnung der Platznummer ====

<code id="60707b3d8ca20">
def index(point: tuple) -> float:
	''' 3) Berechnung Platznummer '''
	appended = str(point[0]) + '.' + str(point[1])
	return float(appended)
</code>

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

<code id="60707b3d8ca89">
def generate_square_numbers():
	n = 1
	while True:
		yield n * n
		n += 1
</code>
<run id="60707b3d8cd14">
square_numbers = generate_square_numbers()
for i in range(20):
	print(next(square_numbers))
</run>

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

<code id="60707b3d8cafa">
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
</code>
<run id="60707b3d8cd6f">
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))
</run>