BuK/IIm20/Vorlesung 12 Grüning

Wiki-Quelltext dieser Seite.

<language>Python</language>
== Kreativaufgabe ==
<code id="60cf2926d7b41">
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
            #print("Combination", combination)
            combination = list(combination)[::-1]
            for index, coeff in enumerate(combination):
                
                sum += coeff * 3 ** index
                #print(str(coeff) + " * 3 ** " + str(index))
            #print("Sum", sum)
            if sum == goed:
                return combination
        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 = ""
    for coeff in p_pred(g(n)):
        ch = ""
        if coeff == 1:
            ch = "a"
        if coeff == 2: 
            ch = "b"
        w += ch
    return w
</code>
<run id="60cf2926d7bbc">
for i in range(1, 11):
    print(g(i))
</run>
<run id="60cf295269eb2">
print(k(5))
</run>