BuK/IIm10/BuK-Kreativaufgabe04 G1

Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
=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:

<math>
\chi ':A^*\rightarrow M
</math>

<math>
\chi_M '(w)=\begin{cases}
true, \text{wenn }w \in M \\
n.d., sonst
\end{cases}
</math>

Diese Funktion ist partiell '''berechenbar'''.

Für die Aufzählbarkeit gilt:

<math>
f: \mathbb{N}_0\rightarrow M
</math>

Diese Funktion ist total, surjektiv und '''berechenbar'''.

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

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

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

Leider kann die Funktion so nicht berechnet werden, da eine Überprüfung von <math>g(i)</math> mit <math>\chi '</math> nicht zu einem Ende kommt, wenn <math>g(i)</math> nicht in <math>M</math> enthalten ist.
Durch die Anwendung zeitbeschränkter Evaluation wie in [[BuK/IIm10/BuK-Übung04 G1#Semi-Entscheidbarkeit | 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.

<code id="4dad5727bd16d" hidden>
;###############   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)))))

</code>

<code id="4dad5727bd1d7">
(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" ))))

</code>

<run id="4dad5727bd26a">
(fm 6)
</run>
BuK/IIm10/BuK-Kreativaufgabe04 G1

Suche
