BuK/IIm10/BuK-Übung04 G1

Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
=Aufzählbarkeit und Entscheidbarkeit=
<language>Scheme</language>
<language>Scheme</language>
==Aufgabenstellung==
Drücken Sie den Beweis des folgenden Satzes mit Racket aus.
Wenn ''M'' eine aufzählbar unendliche Menge ist, dann ist ''M'' semi-entscheidbar.

==Lösung==
<code id="4da47d51a9ef8" 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)))))

;################ buk-impl.rkt #######################
(define A '(#\a #\b #\c))  ; Alphabet

(define g      ; verwendet Alphabet A als freie Variable!!
  (lambda (i)
    (let* ((s (if (< i 2) 1 (ceiling (/ (log i)(log (length A))))))
           (A*-bis-stufe (wortmenge-bis-stufe s A)))
      (list-ref A*-bis-stufe i))))
</code>
<code id="4da47a7597a9d">
(define chi-strich?
  (lambda (w)
    (letrec
        ((helfer
          (lambda (i)
            (if (string=? w (g i))
                #t
                (helfer (+ i 1))))))
      (helfer 0))))
</code>
<run id="4da47a7597b2e">
(chi-strich? "aaa")
</run>
Das nachfolgende Beispiel muss manuel unterbrochen werden, da es sonst ewig laufen würde.
<run id="4da48003d1491">
(chi-strich? "aaa1")
</run>

=Entscheidbarkeit und Aufzählbarkeit=
<language>Scheme</language>
==Aufgabenstellung==
Beweisen Sie: Wenn ''M'' entscheidbar ist, dann sind ''M'' und ''A''* \ ''M'' aufzählbar. Illustrieren Sie anschließend mit Racket.

==Lösung==
<code id="4da481a5cd2fe">
(define chi
  (lambda (n l)
    (if (null? l) 
        #f
        (if (eq? (car l) n)
            #t
            (chi n (cdr l))))))

(define M '(#\a #\b #\c))

(define g_Aufgabe_2
  (lambda (n)
    (cond
      ((> n (- (length M) 1)) null)
      (else
       (list-ref M n)))))

(define f_von_M
  (lambda (n)
    (if(chi (g_Aufgabe_2 n) M)
       (g_Aufgabe_2 n)
       #\a
       )))
</code>
<run id="4da481a5cd377">
(f_von_M 2)
</run>
<run id="4da481c90c358">
(f_von_M 10)
</run>

=Semi-Entscheidbarkeit=
==Aufgabenstellung==
Zeigen Sie auf der Basis der Semi-Entscheidbarkeit, dass wenn ''M'' und ''A''* \ ''M'' aufzählbar sind, ''M'' entscheidbar ist. Repräsentieren Sie den Beweis anschließend mit Racket. Verwenden Sie die entwickelten Racket-Prozeduren für folgendes Beispiel: ''A''* ist die Menge der natürlichen Zahlwörter, ''M'' die Menge der Zahlwörter für die geraden Zahlen und ''A''* \ ''M'' die Zahlwörter für die ungeraden Zahlen.
==Lösung==

Zunächst müssen wir ein neues Alphabet AM definieren und eine Funktion gM(n) die die Wörter über diesem Alphabet aufzählt.

<code>
(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))))
</code>
<run>
(gM 12)
</run>

Nun sind die Chi-Strich Funktionen für M (gerade Zahlen) und A/M (ungerade Zahlen) an der Reihe.

<code>
(define chi-strichM
  (lambda (w)
    (cond
      ((string=? "" w) (chi-strichM w))
      ((let ((char (- (char->integer (string-ref w (- (string-length w) 1))) 48))) (= 0 (modulo char 2)) #t))
      (else
       (chi-strichM w)))))

(define chi-strichA-M 
  (lambda (w)
    (cond 
      ((string=? "" w) (chi-strichA-M w))
      ((let ((char (char->integer (string-ref w (- (string-length w) 1))))) (= 1 (modulo char 2)) #t))
      (else
       (chi-strichA-M w)))))
</code>
<run>
(chi-strichM "12")
;(chi-strichM "13")
</run>

<run>
;(chi-strichA-M "12")
(chi-strichA-M "13")
</run>

Es fehlen nur noch die Funktionen fM(n) und fA-M(n), die mit Hilfe von chi-strichM(w) und chi-strichA-M(w) und g(n), die Menge der geraden bzw. ungeraden Zahlen aufzählen.

<code hidden>

(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))))
</code>
<code>
(define fM
  (lambda (n)
    (let* ((x-y (z-1 n)) (i (car x-y)) (takte (cdr x-y)) (w_i (gM i))
                         (chi_strich_von_g_i_mit_Abbruch (time-ltd-calc (chi-strichM w_i))))
      (chi_strich_von_g_i_mit_Abbruch
       (+ 10 takte)
       (lambda (restzeit resultat) w_i)
       (lambda (berechnungsrest) "0")))))
(define fA-M
  (lambda (n)
    (let* ((x-y (z-1 n)) (i (car x-y)) (takte (cdr x-y)) (w_i (gM i))
                         (chi_strich_von_g_i_mit_Abbruch (time-ltd-calc (chi-strichA-M w_i))))
      (chi_strich_von_g_i_mit_Abbruch
       (+ 10 takte)
       (lambda (restzeit resultat) w_i)
       (lambda (berechnungsrest) "1")))))
</code>
<run>
(fM 5)
</run>
<run>
(fA-M 5)
</run>

Damit ist es nun ein leichtes, die Chi-Funktion mit Hilfe von fM(n) und fA-M(n) anzugeben.

<code>
(define chi-beweis
  (lambda (w)
    (let ((i 1))
      (letrec
           ((helper
             (lambda (n)
               (cond
                 ((string=? w (fM n)) #t)
                 ((string=? w (fA-M n)) #f)
                 (else (helper (+ n 1)))))))
      (helper 0)))))
</code>
<run>
(chi-beweis "13")
</run>
BuK/IIm10/BuK-Übung04 G1

Suche
