Vorlesung 3 Grüning

Aus ProgrammingWiki

Archivierte Version vom 2021-04-02T12:47:35+00:00. Aktuelle Version

Einfache Beispiele für \chi_M

Seite 9 Beispiel 1

def x_m(word):
    return len(word) == 3

print(x_m("a"))

Beispiel 2

def x_m(word):
    if not word:
        return False
    return word[0] == 'a'

print(x_m("babababab"))

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:

def even_enumerable(number):
 return 2*number

Ist bijektiv (lineare Funktion ist bijektiv), total (\forall x \in \mathbf{N}) und berechenbar (da in Python Code)

Prim Zahlen sind aufzählbar:

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))

for i in range(20):
    print(prim(i))

Vorlesung 3 Grüning

Einfache Beispiele für \chi_M

Suche