BuK/IIm20/Vorlesung 8 Seidl

Wiki-Quelltext dieser Seite.

<language>Python</language>
=== S. 4 ===
[[Bild:Fseidl_20210515_151715.jpg]]
[[Bild:Fseidl_20210515_151731.jpg]]

=== S. 11 ===
<code id="609fcbfe9c7ff">
import itertools

# A Generator
alphabet = ["a", "b", "c"]
def a(alphabet):
        for i in range(0, len(alphabet)+1):
            for word in itertools.product(alphabet, repeat=i):
                    yield word


def wort_index(buchstabe, wort):
    for i, w in enumerate(a(wort)):
        if len(w) != 1:
            continue
        if w[0] == buchstabe:
            return i

# Primzahl Generator

def primzahl_generator(n):
    while True:
        if ist_primzahl(n):
            yield n
        n += 1
 
def ist_primzahl(n):
    if n == 2:
        return True

    for i in range(2, n):
        if n % i == 0:
            return False 
    
    return True
    
# Gödelnummer

def get_goedelnummer(wort):
    elemente = []
    for i_b, buchstabe in enumerate(wort):
        primzahl = -1
        for i_p, p in enumerate(primzahl_generator(2)):
            primzahl = p
            if i_b == i_p:
                break
        xi = wort_index(buchstabe, wort)
        elemente.append(primzahl**xi)
    
    produkt = 1
    for faktor in elemente:
        produkt = faktor * produkt
    
    return produkt

# Reverse Gödelnummer (Holzhammer)

def wort_von_goedelnummer(n):
    for w in a(alphabet):
        goedelnummer = get_goedelnummer("".join(w))
        if goedelnummer == n:
            return "".join(w)
</code>

<run id="609fcbfe9c86d">
print(get_goedelnummer("aba"))
print(wort_von_goedelnummer(90))
</run>

=== S. 13 ===
Satz: f ist eine berechenbare Funktion genau dann, wenn h eine berechenbare Funktion ist.

Ausschroten:<br/>
kurz: h = G^−1 ◦ f ◦ G <br/>
ausgeschrieben: h = G^−1(f(G(w)))<br/>

G(w) gibt uns für ein Wort w die zugehörige Gödelnummer i<br/>
f(i) gibt uns für die Gödelnummer i des Wort w eine übertragene Gödelnummer j, welche auch die Gödelnummer des Wortes w' ist<br/>
G^-1(j) gibt uns das Wort w' aus der Gödelnummer von eben dieser (j)<br/>


kurz: f = G ◦ h ◦ G^−1<br/>
ausgeschrieben: f = G(h(G^-1(w'))<br/>

G^-1(w') gibt uns für ein Wort w' die zugehörige Gödelnummer j<br/>
h(j) gibt uns für die Gödelnummer j des Wort w' eine übertragene Gödelnummer i, welche auch die Gödelnummer des Wortes w ist<br/>
G(i) gibt uns das Wort w aus der Gödelnummer von eben dieser (i)<br/>


Bijunktion, <-><br/>

Versuch eines argumentativen Beweises:<br/>

Aus den Eigenschaften (VL 8, S. 4) der Gödelisierung geht hervor, dass G und G^-1 berechenbare Funktionen sind. Fraglich ist somit nur noch, ob f auch berechenbar ist. Bedingung dabei ist, dass f berechenbar ist, genau dann wenn h es auch ist. Mittels h können wir das Wort w' aus dem Wort w ermitteln. Dies ist sozusagen der kurze Berechnungsweg. Der lange Weg über die Gödelisierung geht mittels Funktion G und beinhaltet auch die Funktion f. Wenn wir also das Wort w' aus Wort w berechnen können, so ist auch Funktion f berechenbar, welche uns für die Gödelnummer des Wortes w die Gödelnummer des Wortes w' berechnet.