Vorlesung 3 Grüning

Aus ProgrammingWiki

Archivierte Version vom 2021-04-11T09:37:54+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
8 Seite 24

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

Endliche Mengen aufzählbar

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.

Die Menge G der Gitterpunkte (0, 0), (0, 1), ... einer x-y-Ebene ist aufzählbar.

(0, 0) (1, 0) (0, 1) (0, -1) (1, 1) (-1, 0)

def whole_numbers(n):
    if n == 0:
        return 0
    if n % 2 == 0:
        return int(- (n + 1) / 2 + 0.5)
    else:
        return int((n + 1) / 2)

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

def gitter(n):
    x = 0
    y = 0
    dots = [tuple((whole_numbers(x), whole_numbers(y)))]

    while len(dots) < n:
      x += 1
      dots.append(tuple((whole_numbers(x), whole_numbers(y))))
      while x > 0:
        x -= 1
        y += 1
        dots.append(tuple((whole_numbers(x), whole_numbers(y))))
      y += 1
      dots.append(tuple((whole_numbers(x), whole_numbers(y))))
      while y > 0:
        x += 1
        y -= 1
        dots.append(tuple((whole_numbers(x), whole_numbers(y))))
    return dots
    #0 0
    #1:
    #dann +1 +0
    #solange x -1 +1 bis x = 0
    #dann +0 +1
    #solange +1 -1 bis y = 0    
    #goto 1


def order_gitter(li):
  def compare_tuple(x):
    return (abs(x[0]) + abs(x[1]))

  return sorted(li, key=compare_tuple)


def k(x, y):
  max_value = max(abs(x), abs(y))
  gitter_number = (2 * max_value + 1)**2
  li = gitter(gitter_number)
  li = order_gitter(li)
  print(li)
  for count, value in enumerate(li):
    if value[0] == x and value[1] == y:
      return count

print(k(0, -1))

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

Eine Zahl n kann auf Enthalten sein in der Menge FIBS getestet werden. Da die das nächste Element aus FIBS größer oder gleich dem Vorgnänger ist, kann man nach dem auflisten aller Zahlen aus FIBS die kleiner oder gleich n sind genau feststellen, ob n in FIBS ist oder nicht.

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 int(2 * n)

def odd(n):
    return int(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))

Seite 24

Satz: Die Durchschnittsmenge M1 \cap M2 zweier aufzählbar unendlicher Mengen M1,M2 \subseteq A^* ist eine aufzählbare Menge.

Es ergeben sich drei Szenarien über die Anzahl der Elemente im Schnitt von M1 und M2:

Fall 1: Schnitt ist leer

Das ist Teil der Definition von aufzählbar und somit aufzählbar.

---

Fall 2: Schnitt ist nicht leer und endlich

siehe oben

---

Fall 3: Schnitt ist abzählbar unendlich

Vorlesung 3 Grüning

Inhaltsverzeichnis

Einfache Beispiele für \chi_M

Seite 9

Seite 10

Seite 15

Seite 16

Seite 20

Seite 23

Seite 24

Suche