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$