Vorlesung 3 Grüning

Aus ProgrammingWiki

Archivierte Version vom 2021-04-06T11:09:19+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Einfache Beispiele für \chi_M
2 Seite 9
3 Seite 10
4 Seite 15
5 Seite 16
6 Seite 20
7 Seite 23

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:

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

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

A* ist aufzählbar

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]

print(make_a_star(5, ["a", "b", "c"]))

Anmerkung: make_a_star 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.

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]

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

Seite 20

Halte Problem: Gibt es eine Turingmaschine die festellen kann ob, ein gegebener Algorithmus A für jede mögliche Eingabe x terminiert?

Nicht allgemein entscheidbar \rightarrow aber semi-entscheidbar.

Wenn der Algorithmus für alle Eingaben nach endlicher Zeit terminiert, kann man das Halteproblem für diese Aussage mit "JA" beantworten. Wenn das Programm für auch nur eine Eingabe nicht terminiert kann die Turingmaschine nicht immer feststellen, ob der Algorithmus einfach lange rechnet oder für die Engabe nicht terminieren wird.

FIBS

def FIBS(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2
    return FIBS(n-1) + FIBS(n-2)

for i in range(10):
    print(FIBS(n))

Quadratzahlen QZ

def quad(n):
    return n**n

Jedem x aus X (\mathbf{N})kann sogar genau ein y aus D_f angegeben werden. QZ ist berechenbar, da eine Pythonprozedur angegeben wurde. QZ ist entscheibar, da es eine Notbremse gibt, welche als unmittelbares Abbruchkriteritum gilt. Für eine gegebene Zahl a kann entschieden werden, ob es eine Qudaratzahl ist, da man alle Qudaratzahlen aufzählt die kleiner oder gleich a sind (endliche Menge). Ist a in dieser Menge ist die Antwort "TRUE" andernfalls "FALSE".

Wenn entscheibar, dann ist es auch semi-entscheibar und berechenbar.

Wörter \{a, b\}^* mit a beginnend semientscheibar

Da jeder entscheidbare Algorithmus auch semi-entscheidbar ist und schon oben gezeigt wurde, dass die Menge aller "Wörter aus \{a, b\}^*, die mit 'a' beginnen" entscheidbar ist, ist sie auch semi-entscheidbar.

Seite 23

def even(n):
    return 2 * n

def odd(n):
    return 2 * n + 1

def unite(i, f, g):
    if i % 2 == 0:
        return f(i / 2)
    else:
        return g((i-1) / 2)

for i in range(30):
    print(unite(i, even, odd))

Vorlesung 3 Grüning

Inhaltsverzeichnis

Einfache Beispiele für \chi_M

Seite 9

Seite 10

Seite 15

Seite 16

Seite 20

Seite 23

Suche