Aus ProgrammingWiki

Zeitbeschränkte Prozesse mit Engines

Satz

Wenn M semi-entscheidbar ist, dann ist M aufzählbar.

Beim Analysieren des Satzes erkennt man, dass folgendes gelten soll:

1. M ist semi-entscheidbar
2. M ist aufzählbar

Für die Semi-Entscheidbarkeit gilt:

Diese Funktion ist partiell berechenbar.

Für die Aufzählbarkeit gilt:

Diese Funktion ist total, surjektiv und berechenbar.

Des Weiteren gilt, dass aufzählbar unendlich ist. Das bedeutet, das eine Funktion surjektiv und berechenbar ist.

Die Funktion um den Satz zu beweisen würde wie folgt aufgebaut sein:

Leider kann die Funktion so nicht berechnet werden, da eine Überprüfung von mit nicht zu einem Ende kommt, wenn nicht in enthalten ist. Durch die Anwendung zeitbeschränkter Evaluation wie in Aufgabe 3, kann dieses Problem jedoch behoben werden.

Wie wir bereits festgestellt haben, können wir zeitbeschränkte Evaluation im Wiki leider nicht verwenden und müssen uns einer theoretisch nicht korrekten Variante bedienen.

;############### wortmenge.ss ############ (define wortmenge-stufe (lambda (n alphabet) (if (= n 0) '("") (apply append (map (lambda (zeichen) (map (lambda (wort)(string-append (string zeichen) wort)) (wortmenge-stufe (- n 1) alphabet))) alphabet))))) (define wortmenge-bis-stufe (lambda (n alphabet) (if (= n 0) (wortmenge-stufe 0 alphabet) (append (wortmenge-bis-stufe (- n 1) alphabet) (wortmenge-stufe n alphabet)))))

(define AM '(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9)) ; Alphabet (define gM (lambda (i) (let* ((s (if (< i 2) 1 (ceiling (/ (log i)(log (length AM)))))) (A*-bis-stufe (wortmenge-bis-stufe s AM))) (list-ref A*-bis-stufe i)))) (define pseudo_chi-strichM (lambda (w n) (cond ((= n 0) #f) ((string=? "" w) (pseudo_chi-strichM w (- n 1))) (else (let ((num (- (char->integer (string-ref w (- (string-length w) 1))) 48))) (if (= 0 (modulo num 2)) #t (pseudo_chi-strichM w (- n 1)))))))) (define z (lambda (x y) (+ (/ (* (+ x y)(+ x y 1)) 2) y))) (define z-1 (lambda (n) (letrec ((helfer (lambda (k) (let ((x (- (/ (* k (+ k 3)) 2) n)) (y (- n (/ (* k (+ k 1)) 2)))) (if (and (>= x 0)(>= y 0)) (cons x y) (helfer (+ k 1))))))) (helfer 0)))) (define fM (lambda (n) (let* ((x-y (z-1 n)) (i (car x-y)) (takte (cdr x-y)) (w_i (gM i))) (if (pseudo_chi-strichM w_i (+ 10 takte)) w_i "0" ))))

(fm 6)

ausführen