BuK/IIm20/Vorlesung 8 Grüning

Wiki-Quelltext dieser Seite.

<language>Python</language>
= Gödelisierung Eigenschaften Seite 4 =

Einfach $A^*$ aufzählen (Aufzählfunktion F)und mit G durchprobieren. Umkehrfunktion ist eine Funktion da G injektiv ist. Da G und F berechenbar sind und G(w) garantiert existiert gibt es immer ein Ergebnis.


= Gödelisierung Primzahlverschlüsselung Seite 11 =

<code id="609fadeab8777">
import re

def isPrime(n):
    return re.match(r'^1?$|^(11+?)\1+$', '1' * n) == None

def get_n_primes(N):
    M = 100
    l = list()

    while len(l) < N:
        l += filter(isPrime, range(M - 100, M))
        M += 100
    return l[:N]

def find_char_number(symbol, alphabet):
    for char_index, alpha_char in enumerate(alphabet):
        if alpha_char == symbol:
            return char_index + 1

def G(word, alphabet):
    primes = get_n_primes(len(word))
    prod = 1
    for symbol_index, symbol in enumerate(word):
        char_number = find_char_number(symbol, alphabet)
        prime = primes[symbol_index]
        prod *=  prime**char_number
    return prod
</code>

<run id="609fadeab881c">
A = ["a", "b"]
print(G("aba", A))
</run>

= Kreativaufgabe Seite 27 =

[[Bild:MIU.png]]
Ziel ist es das Wort MU zu erreichen


Textmanipulationen:

1. Füge ein U am Ende eines Satzes ein, welcher mit I endet.

2. Kopiere den Teil eines Satzes, der rechts neben (oder hinter) M steht und füge ihn am rechten Ende an.

3. Ersetze III durch U in einem Satz.

4. Ersetze UU in einem Satz mit ""

MU teil von MIU?

Um auf MU zu kommen muss man die Anzahl der I auf ein Vielfaches von 3 bringen, um sie auf 0 zu reduzieren. Dies ist nötig, da nur Regel 3 Is entfernt.
Jedoch kann man immer nur die Anzahl der Is verdoppeln und da man mit 1, was kein Vielfaches von 3 ist, wird man somit kein Vielfaches von 3 erreichen, da beim Verdoppel immer nur der Primfaktor 2 hinzukommt und durch das zwischenzeitige Subtrahieren von 3 die Anzahl, wenn sie vorher nicht durch 3 teilbar war, garantiert auch nachher nicht durch 3 teilbar sein. Also wird die Anzahl der Is nie durch 3 teilbar sein. Damit kann man MU mit diesen Regeln nicht erzeugen