BuK/IIm20/Vorlesung 3 Grüning

Wiki-Quelltext dieser Seite.

<language>Python</language>
== Einfache Beispiele für $\chi_M$ ==
Seite 9
'''Beispiel 1'''

<code id="6066ffdbf35ec">
def x_m(word):
    return len(word) == 3
</code>
<run id="6066ffdbf36fc">
print(x_m("a"))
</run>


'''Beispiel 2'''

<code id="6066ffdbf3673">
def x_m(word):
    if not word:
        return False
    return word[0] == 'a'

</code>
<run id="6066ffdbf3776">
print(x_m("babababab"))
</run>


'''Seite 10'''
Wie viele berechenbare charakteristische Funktionen gibt es?

Gibt es zu jedem M mindestens ein $\chi_M$ oder auch $\chi_M$ muss nicht entscheidbar sein?

Die Menge aller Teilmengen in A* ist überabzähbar unendlich (Potenzmenge Beweis siehe Vorlesung 2). Dadurch gibt es unendlich viele Mengen M. Dann gibt es mindestens


'''Seite 15'''

Gerade Zahlen sind aufzählbar:
<code id="60671267a7107">
def even_enumerable(number):
 return 2*number
</code>
Ist bijektiv (lineare Funktion ist bijektiv), total ($\forall x \in \mathbf{N}$) und berechenbar (da in Python Code)

Prim Zahlen sind aufzählbar:
<code id="60671267a716c">
import math

def is_prime(n):
    def helper(t):
        if t > math.sqrt(n):
            return True
        if n % t == 0:
            return False
        return helper(t + 2)

    if n == 2:
        return True
    if n <= 1 or n % 2 == 0:
        return False
    return helper(3)

def next_prime(n):
    n += 1
    while not is_prime(n):
        n += 1
    return n


def prim(n):
    if n == 0:
        return 2
    return next_prime(prim(n - 1))
</code>

<run id="60671267a71d3">
for i in range(20):
    print(prim(i))
</run>

<code id="60671bbce098c">
import copy

def make_words(length, alphabet):
    if length == 0:
        return []
    words = copy.copy(alphabet)
    if length == 1:
        return words

    def word_append(word):
        new_words = []
        for letter in alphabet:
            new_words.append(word + letter)
        return new_words

    for word in words:
        for new_word in word_append(word):
            if len(new_word) > length:
                return words
            words.append(new_word)

    return words

def make_a_star(n, alphabet):
    length = 1
    a = []
    if n == 0:
        return alphabet[0]
    while len(a) < n:
        for words in make_words(length, alphabet):
            if len(a) == n:
                return a[n - 1]
            else:
                if words not in a:
                    a.append(words)
        length += 1
    return a[n - 1]
</code>
<run id="60671bbce0a22">
print(make_a_star(5, ["a", "b", "c"]))
</run>

Anmerkung: make_start ist nur surjektiv (das reicht ja aber auch), da 0 und 1 auf den gleichen Wert abgebildet werden.


'''Seite 16'''

Man kann ganz einfach eine Python Prozedur angeben, welche die Werte vorher zugewiesen hat. Alle anderen aus $\mathbf{N}$ die größer als $|M|$ sind werden dem gleichen Element zugewiesen.

<code id="60671ebad7767">
def finite(n):
    M_finite = [...]
    if n == 1:
        return M_finite[1]
    
    if n == 2:
        return M_finite[2]
    ...
    if n == len(M_finite):
        return M_finite[len(M_finite)]
    
    return M_finite[0]
</code>


Alternativ könnte man auch auch $|M|$ Restklassen bilden und diese auf die Elemente zuweisen.