BuK-Übung04 G1

Aus ProgrammingWiki

Archivierte Version vom 2011-04-18T15:26:17+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Aufzählbarkeit und Entscheidbarkeit
- 1.1 Aufgabenstellung
- 1.2 Lösung
2 Entscheidbarkeit und Aufzählbarkeit
- 2.1 Aufgabenstellung
- 2.2 Lösung
3 Semi-Entscheidbarkeit
- 3.1 Aufgabenstellung
- 3.2 Lösung

Aufzählbarkeit und Entscheidbarkeit

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

(define chi-strich?
  (lambda (w)
    (letrec
        ((helfer
          (lambda (i)
            (if (string=? w (g i))
                #t
                (helfer (+ i 1))))))
      (helfer 0))))

(chi-strich? "aaa")

Das nachfolgende Beispiel muss manuel unterbrochen werden, da es sonst ewig laufen würde.

(chi-strich? "aaa1")

Entscheidbarkeit und Aufzählbarkeit

Aufgabenstellung

Beweisen Sie: Wenn M entscheidbar ist, dann sind M und A* \ M aufzählbar. Illustrieren Sie anschließend mit Racket.

Lösung

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

(f_von_M 2)

(f_von_M 10)

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

Für den Nachweis muss eine Funktion implementiert werden, die wie folgt definiert ist:

\chi(w)=\begin{cases} \#t,\text{wenn }f_M(i)=w\\ \#f,\text{wenn }f_{A^*\backslash M}(i)=w \end{cases}

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

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

(gM 12)

Nun sind die Chi-Strich Funktionen für M (gerade Zahlen) und A/M (ungerade Zahlen) an der Reihe. Da die Methoden im Packet 'engines.ss' im Wiki leider nicht funktionieren und somit die, für diesen Beweis erforderliche, zeitbeschränkte Evaluation nicht durchführbar ist, müssen wir uns hier eines, zwar theoretisch falschen, aber dennoch erforderlichen Tricks bedienen. Um die zeitbeschränkte Evaluation zu simulieren, übergeben wir an die beiden Funktionen einfach einen weiteren Parameter, welcher bei jedem erneutem rekursivem Aufruf dekrementiert wird, wobei bei 0 die Funktion #f zurückgibt. Da dies nicht der Definition von chi-strich entspricht, nennen wir diese Methoden einfach pseudo_chi-strich.

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

(define pseudo_chi-strichA-M 
  (lambda (w n)
    (cond
      ((= n 0) #f) 
      ((string=? "" w) (chi-strichA-M w (- n 1)))
      ((let ((char (char->integer (string-ref w (- (string-length w) 1))))) (= 1 (modulo char 2)) #t))
      (else
       (chi-strichA-M w (- n 1))))))

(chi-strichM "12")
;(chi-strichM "13")

;(chi-strichA-M "12")
(chi-strichA-M "13")

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.

(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 start-timer #f)
  (define stop-timer #f)
  (define decrement-timer #f)
  (let ((clock 0) (handler #f))
    (set! start-timer
          (lambda (ticks new-handler)
            (set! handler new-handler)
            (set! clock ticks)))
    (set! stop-timer
          (lambda ()
            (let ((time-left clock))
              (set! clock 0)
              time-left)))
    (set! decrement-timer
          (lambda ()
            (if (> clock 0)
                (begin
                  (set! clock (- clock 1))
                  (if (= clock 0) (handler)))))))
  
  (define make-engine
    (let ((do-complete #f) (do-expire #f))
      (define timer-handler
        (lambda ()
          (start-timer (call/cc do-expire) timer-handler)))
      (define new-engine
        (lambda (resume)
          (lambda (ticks complete expire)
            ((call/cc
              (lambda (escape)
                (set! do-complete
                      (lambda (ticks value)
                        (escape (lambda () (complete ticks value)))))
                (set! do-expire
                      (lambda (resume)
                        (escape (lambda ()
                                  (expire (new-engine resume))))))
                (resume ticks)))))))
      (lambda (proc)
        (new-engine
         (lambda (ticks)
           (start-timer ticks timer-handler)
           (let ((value (proc)))
             (let ((ticks (stop-timer)))
               (do-complete ticks value))))))))

;  (define-syntax timed-apply
;    (syntax-rules ()
;      ((_ exp ... )
;       (begin (decrement-timer)
;              (#%plain-app exp ...)))))


  (define mileage
    (lambda (thunk)
      (let loop ((eng (make-engine thunk)) (total-ticks 0))
        (eng 50
             (lambda (ticks value)
               (+ total-ticks (- 50 ticks)))
             (lambda (new-eng)
               (loop new-eng (+ total-ticks 50)))))))
  
  (define-syntax time-ltd-calc
    (syntax-rules ()
      ((_ calc) (make-engine (lambda () calc)))))

(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 (chi-strichM w_i (+ 10 takte))))
      ((if (chi_strich_von_g_i) w_i "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 (chi-strichA-M w_i (+ 10 takte))))
      ((if (chi_strich_von_g_i) w_i "1")))))

(fM 5)

(fA-M 5)

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

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

(chi-beweis "13")

BuK-Übung04 G1

Inhaltsverzeichnis

Aufzählbarkeit und Entscheidbarkeit

Aufgabenstellung

Lösung

Entscheidbarkeit und Aufzählbarkeit

Aufgabenstellung

Lösung

Semi-Entscheidbarkeit

Aufgabenstellung

Lösung

Suche