Aus ProgrammingWiki

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 Kreativaufgabe Seite 24

Einfache Beispiele für $\chi_M$

Seite 9

Beispiel 1

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

print(x_m("a"))

ausführen

Beispiel 2

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

print(x_m("babababab"))

ausführen

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

ausführen

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

ausführen

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

ausführen

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

ausführen

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

ausführen

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

ausführen

Kreativaufgabe 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:

Schnitt ist leer Dann ist er per Definition aufzählbar.

Durch die Semi-Entscheidbarkeit der Frage $x \in M1$ bzw. $x \in M2$ kann man den Schnitt nicht so einfach feststellen. Wenn man das Festellen kann, dann würde man überprüfen ob f1(0) in M2 wenn ja: 0 -> f1(0) dann würde man prüfen, ob f2(0) in M1 ist, wenn ja 1 -> f2(0) und so weiter.

Überlegungen:

Kann man wenn man $f^-$ bilden kann festellen, ob f1(x) auch in M2 ist und umgegehrt? Durch die Surjektivität von f1 und f2 muss es jedoch nicht unbedingt eine Umkehrfunktion geben.

Satz aus Vorlesung 4: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.

Damit ein Word $w$ im Schnitt enthalten ist, dann ist es mindestens in M1 enthalten.

Man zählt M1 auf und überprüft mit $\chi'_{M2}$, ob $w \in M1$ auch in M2 enthalten ist. Wenn $\chi'_{M2}$ wahr liefert ist das Element in der Schnittmenge und kann somit dem $n$ welches gerade zum Aufzählen von $M1$ verwendet wird, abgebildet werden. Wenn es nicht terminiert, dann ist es nicht in $M2$ und somit auch nicht im Schnitt. Damit ist der Schnitt semi-entscheidbar und damit auch aufzählbar.