BuK-Kreativaufgabe04 G1

Aus ProgrammingWiki

< BuK < IIm10

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:

M ist semi-entscheidbar
M ist aufzählbar

Für die Semi-Entscheidbarkeit gilt:

\chi ':A^*\rightarrow M \chi_M '(w)=\begin{cases} true, \text{wenn }w \in M \\ n.d., sonst \end{cases}

Diese Funktion ist partiell berechenbar.

Für die Aufzählbarkeit gilt:

f: \mathbb{N}_0\rightarrow M

Diese Funktion ist total, surjektiv und berechenbar.

Des Weiteren gilt, dass A^* aufzählbar unendlich ist. Das bedeutet, das eine Funktion g: \mathbb{N}_0 \rightarrow A^* surjektiv und berechenbar ist.

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

f(i)=\begin{cases} g(i),\text{wenn } \chi_M '(g(i))\\ a \in M, \text{sonst} \end{cases}

Leider kann die Funktion so nicht berechnet werden, da eine Überprüfung von g(i) mit \chi ' nicht zu einem Ende kommt, wenn g(i) nicht in M 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.

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

BuK-Kreativaufgabe04 G1

Zeitbeschränkte Prozesse mit Engines

Suche