Vorlesung 4 Lemke

Aus ProgrammingWiki

< BuK < IIm20

Archivierte Version vom 2021-04-17T19:11:38+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Übungsaufgabe S. 11
- 1.1 Beispiel Ermittlung x und y aus z
2 Kreativaufgabe S. 15
- 2.1 Aufzählfunktion für semi-entscheidbare Menge
3 Übungsaufgabe S. 26
- 3.1 Beweis Wenn die Menge M entscheidbar ist, dann ist M aufzählbar
4 Übungsaufgabe S. 32
- 4.1 Illustration Beweis: Wenn M und A*\M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge

Übungsaufgabe S. 11

Beispiel Ermittlung x und y aus z

Kreativaufgabe S. 15

Aufzählfunktion für semi-entscheidbare Menge

Achtung, dieser Code funktioniert nur auf UNIX-Systemen.

import signal

from itertools import product
from math import sqrt

ALPHABET = ['a', 'b', 'c']
a = 'abab'

def timeout(signum, frame):
	raise Exception('Stop waiting')

def semi_chi(word):
	if word.startswith('ab'):
		return True
	else:
		while True:
			pass
			
def generate_words_with_length(length):
	return ["".join(x) for x in product(ALPHABET, repeat=length)]
			
def generate_wordset():
	length = 0
	while True:
		for w in generate_words_with_length(length):
			yield w
		length += 1
		
def get_word_at(wordset, index):
	for i in range(index+1):
		w = next(wordset)
		if i == index:
			return w
			
def get_x_y_from_z(z):
	w = int((sqrt(8 * z + 1) -1) / 2)
	t = int((w * (w + 1)) / 2) # has to be typecast bc otherwise it will be .0 float
	y = z - t
	x = w - y
	return (x, y)
	
def generate_M(z):
	x, y = get_x_y_from_z(z)
	signal.signal(signal.SIGALRM, timeout)
	signal.alarm(y+1)
	try:
		word = get_word_at(generate_wordset(), x)
		if semi_chi(word):
			return word
	except Exception:
		return a

for z in range(20):
	print(generate_M(z))

Übungsaufgabe S. 26

Beweis Wenn die Menge M entscheidbar ist, dann ist M aufzählbar

entscheidbar: Es gibt eine totale, berechenbare charakteristische Funktion, die für jedes Wort aus der Wortmenge A* entscheidet, ob es in der Menge M ist oder nicht.
aufzählbar: Es gibt eine totale, berechenbare surjektive Funktion, die die natürlichen Zahlen auf alle Elemente aus M abbildet

Zu zeigen: Wenn M entscheidbar, dann M aufzählbar

Wir haben also eine Menge M, von der wir wissen, dass sie berechenbar ist. Das heißt, es gibt eine charakteristische Funktion, die uns für jedes beliebige Wort aus A* ein wahr oder falsch zurückgibt, je nachdem, ob das Wort in M ist oder nicht.

Wir können nun eine Aufzählfunktion konstruieren. Diese totale, berechenbare, surjektive Funktion muss die natürlichen Zahlen auf die Elemente von M abbilden. Anders gesagt, für jede natürliche Zahl generiert sie ein dazugehöriges Element von M, wir können mit ihr die gesamte Menge generieren.

Mithilfe der vorhandenen charakteristischen Funktion können wir folgende Aufzählfunktion schreiben:

'''
def generate_set(wordset, chi):
	for word in wordset:
		if chi(word) == True:
			yield word
'''

Somit haben wir bewiesen, dass wir aus der Eigenschaft der Entscheidbarkeit ableiten können, dass eine Menge auch aufzählbar ist.

Nun ist auch zu zeigen, dass das Umgekehrte auch nicht gilt. D.h. wir können nicht schlussfolgern, dass eine beliebige Menge entscheidbar ist, wenn wir wissen, dass sie aufzählbar ist.

An dieser Stelle können wir auf den zuvor gebrachten Beweis (S. 2-13) verweisen. Hier hatten wir gezeigt, dass jede aufzählbare Menge auch semi-entscheidbar ist und jede semi-entscheidbare auch aufzählbar. Dadurch, dass hier die Semi-Entscheidbarkeit schon ausreicht, können wir nicht die Entscheidbarkeit aus der Aufzählbarkeit einer Menge folgern.

Übungsaufgabe S. 32

Illustration Beweis: Wenn M und A*\M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge

def chi_from_generators(word, M_generator, not_M_generator):
	while True:
		if word == next(M_generator):
			return True
		elif word == next(not_M_generator):
			return False
			
def generate_odd_numbers():
	n = 1
	while True:
		yield n
		n += 2
		
def generate_not_odd_numbers():
	n = 0
	while True:
		yield n
		n += 2

test_word = 4
print(chi_from_generators(test_word, generate_odd_numbers(), generate_not_odd_numbers()))

Vorlesung 4 Lemke

Inhaltsverzeichnis

Übungsaufgabe S. 11

Beispiel Ermittlung x und y aus z

Kreativaufgabe S. 15

Aufzählfunktion für semi-entscheidbare Menge

Übungsaufgabe S. 26

Beweis Wenn die Menge M entscheidbar ist, dann ist M aufzählbar

Übungsaufgabe S. 32

Illustration Beweis: Wenn M und A*\M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge

Suche