BuK/IIm20/Vorlesung 4 Thomas

Wiki-Quelltext dieser Seite.

<language>Python</language>
= 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$

<code id="607c118148df5">
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)
</code>
<run id="607c118148e79">
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)))
</run>

= 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 =
<code id="607c2a19575bf">
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
</code>
<run id="607c2a195763a">
menge_bis(M, 10)
menge_bis(A_M, 10)

chi_M(50)
chi_M(51)
chi_M(9199)
</run>