Vorlesung 4 Thomas

Aus ProgrammingWiki

Archivierte Version vom 2021-04-18T11:38:28+00:00. Aktuelle Version

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

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

Vorlesung 4 Thomas

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

Seite 26

Suche