BuK/IIm20/Vorlesung 4 Thomas

Wiki-Quelltext dieser Seite.

<language>Python</language>
= Ab-, Aufzählbarkeit, Semi-Entscheidbarkeit, Entscheidbarkeit =


Ü1

$z = \pi(1,3) = \frac{(x+y)(x+y+1)}{2} + y = \frac{(1+3)(1+3+1)}{2} + 3 = 10 + 3 = 13$

<code id="607c118148df5">
import math

def cantorPaar(x, y):
    return (int)(((x+y)*(x+y+1))/2) + y

def getXCantorPaar(z):
    w = math.floor((math.sqrt(8*z+1)-1)/2)
    t = (w * (w + 1))/2
    y = z - t
    return (int)(w - y)

def getYCantorPaar(z):
    w = math.floor((math.sqrt(8*z+1)-1)/2)
    t = (w * (w + 1))/2
    return (int)(z - t)
</code>
<run id="607c118148e79">
print(cantorPaar(2, 3))
print(getXCantorPaar(cantorPaar(2, 3)))
print(getYCantorPaar(cantorPaar(2, 3)))

print(cantorPaar(1, 3))
print(getXCantorPaar(cantorPaar(1, 3)))
print(getYCantorPaar(cantorPaar(1, 3)))
</run>

= Seite 26 =

Wenn die Menge $M$ entscheidbar ist, dann ist $M$ aufzählbar.

entscheidbar: Prozedur $\chi$ gibt für jedes eingegeben Wort $w$ aus $A^*$ nach endlicher Zeit ein Ergebnis (#t/#f) aus

aufzählbar: eine total berechenbare surjektive Funktion $f: N \rightarrow M$

TODO

= Seite 27 =
Eine Menge $M$ ist entscheidbar genau dann, wenn $M$ und $A^∗ \ M$ (Komplementmenge) aufzählbare Mengen sind.

Teil 1:

Wenn $M$ eine entscheidbare Menge ist, dann sind $M$ und $A^∗ \setminus M$ aufzählbare Mengen.

$M$ entscheidbar $\rightarrow$ $M$ und $A^∗ \setminus M$ aufzählbar

entscheidbar: Prozedur $\chi$ gibt für jedes eingegeben Wort $w$ aus $A^*$ nach endlicher Zeit ein Ergebnis (#t/#f) aus

aufzählbar: eine total berechenbare surjektive Funktion $f: N \rightarrow M$


Teil 2:

$M$ entscheidbar $\leftarrow$ $M$ und $A^∗ \setminus M$ aufzählbar

= Seite 32 =
<code id="607c2a19575bf">
def M(n):
    return 2*n+1

def A_M(n):
    return 2*n

def menge_bis(M, n):
    print([M(i) for i in range(n)])

def chi_M(n):
    c=0
    while True:
        if M(c) == n:
            return print(True)
        if A_M(c) == n:
            return print(False)
        c+=1
</code>
<run id="607c2a195763a">
menge_bis(M, 10)
menge_bis(A_M, 10)

chi_M(50)
chi_M(51)
chi_M(9199)
</run>

= KA =
<code id="607c96c01337d">
import math

alphabet = ['a','b','c']

def cantorPaar(x, y):
    return (int)(((x+y)*(x+y+1))/2) + y

def getXCantorPaar(z):
    w = math.floor((math.sqrt(8*z+1)-1)/2)
    t = (w * (w + 1))/2
    y = z - t
    return (int)(w - y)

def getYCantorPaar(z):
    w = math.floor((math.sqrt(8*z+1)-1)/2)
    t = (w * (w + 1))/2
    return (int)(z - t)

def generate_a_star(A, count):
    A_star = []
    for s in A:
        A_star.append(s)
    for i in range(0, count):
        A_star_temp = A_star.copy()
        for p in A_star_temp:
            for s in A:
                if (p + s) not in A_star:
                    A_star.append(p + s)
    A_star.append("")
    return A_star

def g(x):
    c = 1
    while True:
        A_Star = generate_a_star(alphabet, c)
        if len(A_Star) > x:
            return A_Star[x]
        else:
            c+=1

def chi(w):
    if len(w) >= 2:
        if w[0] == 'a' and w[1] == 'b':
            return True
    return False


def f(z):
    c = 0
    i = 0
    while True:
        x = getXCantorPaar(c)
        y = getYCantorPaar(c)
        w = g(x)
        #print("w = g(",x,"): " , w)
        if chi(w) is True:
            i+=1
            print(w)
        
        c+=1
        if i>=z:
            return
</code>
<run id="607c96c013408">
f(500)
</run>