Aus ProgrammingWiki

Inhaltsverzeichnis 1 Ab-, Aufzählbarkeit, Semi-Entscheidbarkeit, Entscheidbarkeit 2 Seite 26 3 Seite 27 4 Seite 32 5 KA

Ab-, Aufzählbarkeit, Semi-Entscheidbarkeit, Entscheidbarkeit

Ü1

$z = \pi(1,3) = \frac{(x+y)(x+y+1)}{2} + y = \frac{(1+3)(1+3+1)}{2} + 3 = 10 + 3 = 13$

import math def cantorPaar(x, y): return (int)(((x+y)*(x+y+1))/2) + y def getXCantorPaar(z): w = math.floor((math.sqrt(8*z+1)-1)/2) t = (w * (w + 1))/2 y = z - t return (int)(w - y) def getYCantorPaar(z): w = math.floor((math.sqrt(8*z+1)-1)/2) t = (w * (w + 1))/2 return (int)(z - t)

print(cantorPaar(2, 3)) print(getXCantorPaar(cantorPaar(2, 3))) print(getYCantorPaar(cantorPaar(2, 3))) print(cantorPaar(1, 3)) print(getXCantorPaar(cantorPaar(1, 3))) print(getYCantorPaar(cantorPaar(1, 3)))

ausführen

Seite 26

Wenn die Menge $M$ entscheidbar ist, dann ist $M$ aufzählbar.

entscheidbar: Prozedur $\chi$ gibt für jedes eingegeben Wort $w$ aus $A^*$ nach endlicher Zeit ein Ergebnis (#t/#f) aus

aufzählbar: eine total berechenbare surjektive Funktion $f: N \rightarrow M$

TODO

Seite 27

Eine Menge $M$ ist entscheidbar genau dann, wenn $M$ und $A^∗ \ M$ (Komplementmenge) aufzählbare Mengen sind.

Teil 1:

Wenn $M$ eine entscheidbare Menge ist, dann sind $M$ und $A^∗ \setminus M$ aufzählbare Mengen.

$M$ entscheidbar $\rightarrow$ $M$ und $A^∗ \setminus M$ aufzählbar

entscheidbar: Prozedur $\chi$ gibt für jedes eingegeben Wort $w$ aus $A^*$ nach endlicher Zeit ein Ergebnis (#t/#f) aus

aufzählbar: eine total berechenbare surjektive Funktion $f: N \rightarrow M$

Teil 2:

$M$ entscheidbar $\leftarrow$ $M$ und $A^∗ \setminus M$ aufzählbar

Seite 32

def M(n): return 2*n+1 def A_M(n): return 2*n def menge_bis(M, n): print([M(i) for i in range(n)]) def chi_M(n): c=0 while True: if M(c) == n: return print(True) if A_M(c) == n: return print(False) c+=1

menge_bis(M, 10) menge_bis(A_M, 10) chi_M(50) chi_M(51) chi_M(9199)

ausführen

KA

import math alphabet = ['a','b','c'] def cantorPaar(x, y): return (int)(((x+y)*(x+y+1))/2) + y def getXCantorPaar(z): w = math.floor((math.sqrt(8*z+1)-1)/2) t = (w * (w + 1))/2 y = z - t return (int)(w - y) def getYCantorPaar(z): w = math.floor((math.sqrt(8*z+1)-1)/2) t = (w * (w + 1))/2 return (int)(z - t) def generate_a_star(A, count): A_star = [] for s in A: A_star.append(s) for i in range(0, count): A_star_temp = A_star.copy() for p in A_star_temp: for s in A: if (p + s) not in A_star: A_star.append(p + s) A_star.append("") return A_star def g(x): c = 1 while True: A_Star = generate_a_star(alphabet, c) if len(A_Star) > x: return A_Star[x] else: c+=1 def chi(w): if len(w) >= 2: if w[0] == 'a' and w[1] == 'b': return True return False def f(z): c = 0 i = 0 while True: x = getXCantorPaar(c) y = getYCantorPaar(c) w = g(x) #print("w = g(",x,"): " , w) if chi(w) is True: i+=1 print(w) c+=1 if i>=z: return

f(500)

ausführen