Vorlesung 3 Nerlich

Aus ProgrammingWiki

Inhaltsverzeichnis

1 S.9
2 S.10
3 S.15–16 (Aufzählbarkeit)
4 S.20
5 S.23

S.9

#/usr/bin/env python3

from random import Random


class WordGenerator:
	"""docstring for WordGenerator"""
	def __init__(self, alphabet: set):
		if not alphabet.isdisjoint({None}):
			raise ValueError("The alphabet cannot contain None")
		
		self._alphabet = frozenset(alphabet)
		self._generator = Random()
		self._word = ""
		self._ended = False
		
	def __iter__(self):
		return self
		
	def __next__(self):
		result = self._generator.choice(tuple(self._alphabet.union({None})))
		if result is None or self._ended:
			self._ended = True
			raise StopIteration()
		else:
			self._word = self._word + result
			return result
		
	@property
	def alphabet(self) -> frozenset:
		return self._alphabet
	
	@property
	def word(self):
		while not self._ended:
			try:
				next(self)
			except StopIteration:
				pass
		return self._word
		
	def next(self):
		return self.__next__()
		
	def reset(self):
		self._word = ""
		self._ended = False


def chi_length_3(w: WordGenerator):  # requires at most 4 checks
	for n in range(1,4):
		try:
			
			print("Letter #{} is '{}'".format(n, next(w)))  # up to 3 checks, determining lengths 0 to 2
			
		except StopIteration:
			print("Word '{}' is of length shorter than 3!".format(w.word))
			return False
	try:
		
		print("Letter #4 is '{}'".format(next(w)))  # fourth check shows whether of length 3
		
		print("Word '{}' is of length longer than 3!".format(w.word))
		return False
	except StopIteration:
		print("Word '{}' is of length 3.".format(w.word))
		return True

def chi_starts_with_letter(w: WordGenerator, letter):  # always requires only one check
	try:
		
		result = next(w)  # one check
		
		print("Letter #1 is '{}'".format(result))
		if result == letter:
			print("Word '{}' starts with '{}'!".format(w.word, letter))
			return True
		else:
			print("Word '{}' does not start with '{}'.".format(w.word, letter))
			return False
	except StopIteration:
		print("Word '{}' does not start at all.".format(w.word))
		return False


A = {'a', 'b'}

chi_length_3(WordGenerator(A))

chi_starts_with_letter(WordGenerator(A), 'a')

S.10

Berechenbarkeit := \exists Algorithmus, der für jedes x \in D_f den Funktionswert f effektiv ermittelt (effektiv = es muss ein entsprechendes Verfahren geben)

A	endlich
A^\ast	abzählbar unendlich
\mathcal{P}(A^\ast)	überabzählbar unendlich
\chi_M	überabzählbar unendlich
\chi_M berechenbar	?????
\chi_M implementierbar	abzählbar unendlich

S.15–16 (Aufzählbarkeit)

G (gerade Zahlen)

G \subset \mathbb{N}

kann \mathbb{N} auf G abbilden: 0→0, 1→2, 2→4, etc.

P (Primzahlen)

P \subset \mathbb{N}, \exists berechenbare Methode für Entscheidung n \in P \hspace{4mm} \longrightarrow \hspace{4mm} f: durchprobieren

A^\ast

trivial: längenlexikografisch aufzählen

\forall endliche Menge

nehme beliebiges Element e aus Menge M und bilde damit eine neue Menge M' (beim ersten Mal also: M' = \{e\})

wiederhole für Restmenge M \backslash M', bis M \backslash M' = \empty

G = \{(0,0), (0,1), \ldots\}

[1] f: \mathbb{N} \mapsto G bijektiv

Diagonalisierung: \mathbb{Z} \times \mathbb{Z}

[2] Ordnungsrelation p_<

p_<(g_1, g_2) :\ <\!(f^{-1}(g_1), f^{-1}(g_2))

[3] k: Platznummern

trivial: k := f^{-1}

[4] Aufzählprozedur{}_G, Berechenbarkeit?

f implementieren:

def grid():
	yield (0, 0)
	x = 0
	y = 1
	phase = 0
	while True:
		if phase % 4 == 0:
			x = x+1
			y = y-1
			if y == 0:
				phase = phase+1
		elif phase % 4 == 1:
			x = x-1
			y = y-1
			if x == 0:
				phase = phase+1
		elif phase % 4 == 2:
			x = x-1
			y = y+1
			if y == 0:
				phase = phase+1
		elif phase % 4 == 3:
			x = x+1
			y = y+1
			if x == 0:
				phase = phase+1
		yield (x, y)
		if phase % 4 == 0 and x == 0:
			y = y+1

g = grid()

for i in range(0, 20):
	print(next(g))

Berechenbarkeit: trivial

S.20

Halteproblem semi-entscheidbar

Immer, wenn das Programm terminiert, kann in endlicher Zeit eine Antwort gegeben werden.

FIBS

Aufzählfunktion f: (nach Berechnungsvorschrift)

siehe Definition Berechenbarkeit, Aufzählfunktion ermittelt effektiv Funktionswert

semi-entscheidbar: \chi'_M : \begin{cases} \text{True}, & f\ \text{liefert Wert;}\\ \perp, & \text{else.}\end{cases}

entscheidbar: f(x) < f(x+1)\ \forall x \in \mathbb{N} \Longrightarrow f(x) < g < f(x+1) \rightarrow g \not\in FIBS für gesuchtes g

QZ

Aufzählfunktion q: nach Berechnungsvorschrift