Vorlesung 4 Seidl

Aus ProgrammingWiki

Inhaltsverzeichnis 1 KA 2 S. 26 3 S. 28 4 S. 32 5 S. 33

KA

from itertools import product from browser import timer import math a = ["a", "b", "c"] def paarungsfunktion(i): z = i w = math.trunc((math.sqrt(8 * z + 1) - 1) / 2) t = (w * (w + 1)) / 2 y = z - t x = w - y return (x, y) def g(generator, index): count = -1 for w in generator(): count += 1 if count == index: return w def a_stern(): count = 0 while True: for w in product(a, repeat=count): yield "".join(w) count += 1 def chi_strich(wort, ticks): if wort.startswith("ab") is True: return True else: for i in range(0, ticks): timer.set_timeout(None, 1) return def f(z): count = 0 while True: wort_index, ticks = paarungsfunktion(count) wort = g(a_stern, wort_index) wert = chi_strich(wort, int(ticks)) if wert is True: print(wort) else: print("abc") count += 1 if count >= z: return

f(5000)

ausführen

S. 26

Wenn es möglich ist eine Funktion chi zu schreiben, die entscheidet, ob das der Funktion chi per Parameter übergebene Wort Teil der Menge M ist oder nicht, so kann diese Funktion chi genutzt werden, um beim Generieren von A* zu prüfen, ob das jeweilig generierte Wort Teil von der Menge M ist. Damit ist M entscheidbar. Ist dies der Fall, so wird das Wort zurückgegeben und weiter verfahren. Auf diese Weise ist M auch aufzählbar. Damit ist wenn die Menge M entscheidbar ist, M auch aufzählbar.

import random def chi(wort): enthalten = random.choice([True, False]) if enthalten is True: return True else: return False def generator_m(): for wort in a_stern: if chi(wort) is True: yield wort

Fraglich ist zunächst, wenn M aufzählbar ist, ob M dann auch entscheidbar ist.
Im Beweis von Satz 1, Teil 1 wurde bewiesen, dass wenn eine Menge M aufzählbar ist, dass dann M semi-entscheidbar ist. Wenn eine Menge semi-entscheidbar ist, dann folgt daraus, dass sie nicht entscheidbar ist.
Damit ist wenn M aufzählbar ist, M nicht automatisch entscheidbar.

S. 28

import random def chi(wort): enthalten = random.choice([True, False]) if enthalten is True: return True else: return False def generator_m(): for wort in a_stern: if chi(wort) is True: yield wort def generator_a_stern_minus_m(): for wort in a_stern: if chi(wort) is False: yield wort

S. 32

# Menge Menge A*-M def generate_gerade(): count = 0 while True: yield count count += 2 # Menge M def generate_ungerade(): count = 1 while True: yield count count += 2 def wort_an_index_in_gerade(index): count = 0 for wort in generate_gerade(): if count == index: return wort count += 1 # Charakteristische Funktion M entscheidbar def chi(wort): i = 0 for gen_wort in generate_ungerade(): if wort == gen_wort: return True if wort == wort_an_index_in_gerade(i): return False i += 1

print(chi(9199))

ausführen

S. 33

p(A):

       - A ist ein endliches Alphabet: [a, b]
       - Potenzmenge von A sind alle möglichen Kombinationen (Wörter) aus A + leere Menge: [ , a, b, aa, ab, ..., bb]

p(A*):

       - A* ist eine unendliche Wortmenge
       - Potenzmenge von A* sind alle möglichen Kombinationen (Wörter) aus A* + leere Menge (überabzählbar unendlich?)

A*:

       - A* sind unendlich viele Kombinationen (Wörter) aus A ohne Längenbegrenzung
       - z.B. [ , a, aa, aaa, aaaa, aaaaa, ...]

endliche Menge (abzählbar unendlich viele):

       - [[ , a, b, aa, ab, ..., bb], [ , c, d, cc, cd, ..., dd], ...]

entscheidbare Menge (abzählbar unendlich viele):

       - muss größer als semi-entscheidbare Menge (abzählbar unendlich viele) sein, weil Entscheidbarkeit impliziert semi-Entscheidbarkeit

aufzählbare Menge (abzählbar unendlich viele):

       - [[a, b, ab, ...], [b, c, bc, ...], ...]

abzählbare Menge (überabzählbar unendlich viele):

       - [[a, b, ab, ...], ..., [b, c, bc, ...], ...]

Von größer zu kleiner: p(A*)
abzählbare Menge (überabzählbar unendlich viele)
aufzählbare Menge (abzählbar unendlich viele) - entscheidbare Menge (abzählbar unendlich viele)
semi-entscheidbare Menge (abzählbar unendlich viele)
endliche Menge (abzählbar unendlich viele)
A*
p(A)