Vorlesung 3 Nerlich

Aus ProgrammingWiki

Inhaltsverzeichnis 1 S.9 2 S.10 3 S.15–16 (Aufzählbarkeit) 3.1 $G$ (gerade Zahlen) 3.2 $P$ (Primzahlen) 3.3 $A^\ast$ 3.4 $\forall$ endliche Menge 3.5 $G = \{(0,0), (0,1), \ldots\}$ 4 S.20 4.1 Halteproblem semi-entscheidbar 4.2 $FIBS$ 4.3 $QZ$ 4.4 $M = \{a, b\}^\ast | w = a \cdot w'\ \forall w \in M$ 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))

ausführen

chi_starts_with_letter(WordGenerator(A), 'a')

ausführen

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

ausführen

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

siehe Definition Berechenbarkeit, Aufzählfunktion ermittelt effektiv Funktionswert

semi-entscheidbar: $\chi'_{QZ} : \begin{cases} \text{True}, & q\ \text{liefert Wert;}\\ \perp, & \text{else.}\end{cases}$

$q(x) < q(x+1)\ \forall x \in \mathbb{N} \Longrightarrow q(x) < g < q(x+1) \rightarrow g \not\in QZ$ für gesuchtes $g$

$M = \{a, b\}^\ast | w = a \cdot w'\ \forall w \in M$

siehe oben, entscheidbar $\Rightarrow$ semi-entscheidbar

S.23

def even(): x = 0 while True: yield(x) x = x+2 def odd(): x = 1 while True: yield(x) x = x+2 def both(): e = even() o = odd() while True: yield(next(e)) yield(next(o)) b = both()

for i in range(0, 30): print(next(b))

ausführen