Vorlesung 12 Grüning

Aus ProgrammingWiki

Kreativaufgabe

from itertools import product

def h(w):
    """Gödelisierung"""
    sum = 0
    for index, ch in enumerate(w):
        ko = 0
        if ch == "a":
            ko = 1
        if ch == "b":
            ko = 2
        sum += ko * 3 ** (len(w) - index - 1)
    return sum

def p_pred(goed):
    """Prädikat testet, ob eine natürliche Zahl Gödelnummer ist"""
    n = 0
    sum = 0
    while sum < goed:
        for combination in product([1, 2], repeat = n):
            sum = 0
            #combination = list(combination)[::-1]
            #print("Combination", combination)
            for index, coeff in enumerate(combination):
                
                sum += coeff * 3 ** index
                #print(str(coeff) + " * 3 ** " + str(index))
            #print("Sum", sum, "=", goed, "?")
            if sum == goed:
                return list(combination)[::-1]
        n += 1
    return []

def p(r, y):
    if p_pred(y) and r <= y:
        return 1
    return 0

def g(n):
    """Folge der Gödelnummern"""
    def f(p1, p2):
        m = 0
        while True:
            minus = 1 - p(p1, m)
            if minus < 0:
                minus = 0
            if minus == 0:
                #print("return f", m)
                return m
            m += 1

    if n == 1:
        ret = f(0, n)
        #print("return n==1", ret)
        return ret
    else:
        res = f(g(n - 1) + 1, n)
        #print("return else", res)
        return res

def k(n):
    """k(n) = h^-1(g(n))"""
    w = ""
    coeffs = p_pred(n)
    print(coeffs)
    for coeff in coeffs:
        ch = ""
        if coeff == 1:
            ch = "a"
        if coeff == 2: 
            ch = "b"
        w += ch
    return w

w = "a"
goedel_number = h(w)

#h(w): Goedelnummer zu w
#g(n): n-te Goedelnummer
#k(n): w zur n-ten Goedelnummer


w = "abb"
print("w", w)
goedel_number = h(w)
print("goedel_number", goedel_number)
print("g", g(goedel_number))
print(k(goedel_number))

for i in range(1, 11):
    print(g(i))

Vorlesung 12 Grüning

Kreativaufgabe

Suche