Vorlesung 3 Grüning

Aus ProgrammingWiki

Archivierte Version vom 2021-04-05T09:16:02+00:00. Aktuelle Version

Inhaltsverzeichnis

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

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

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

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

Da jede entscheidbarkeit auch semi entscheidbar ist

Vorlesung 3 Grüning

Inhaltsverzeichnis

Einfache Beispiele für \chi_M

Seite 10

Seite 15

Seite 16

Seite 20

Suche