BuK/IIm20/Vorlesung 4 Seidl

Wiki-Quelltext dieser Seite.

<language>Python</language>
=== KA ===
<code id="607b30f0aee5d">
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
</code>
<run id="607b30f0aeec2">f(5000)</run>

=== 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.<br/><br/>

<code id="607c3a2fb376d">
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

</code>

Fraglich ist zunächst, wenn M aufzählbar ist, ob M dann auch entscheidbar ist.<br/>
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.<br/>
Damit ist wenn M aufzählbar ist, M nicht automatisch entscheidbar.

=== S. 28 ===
<code id="607c3a5ea492d">
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
</code>

=== S. 32 ===
<code id="607c43cd09856">
# 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
</code>
<run id="607c43cd09908">
print(chi(9199))
</run>

=== 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*)<br/>
abzählbare Menge (überabzählbar unendlich viele)<br/>
aufzählbare Menge (abzählbar unendlich viele) - entscheidbare Menge (abzählbar unendlich viele)<br/>
semi-entscheidbare Menge (abzählbar unendlich viele)<br/>
endliche Menge (abzählbar unendlich viele)<br/>
A*<br/>
p(A)<br/>