Vorlesung 4 Thomas

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Ab-, Aufzählbarkeit, Semi-Entscheidbarkeit, Entscheidbarkeit
2 Seite 26
3 Seite 27
4 Seite 32
5 KA

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

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)

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

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

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

menge_bis(M, 10)
menge_bis(A_M, 10)

chi_M(50)
chi_M(51)
chi_M(9199)

KA

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

f(500)