BuK-Übung04 G1

Aus ProgrammingWiki

Archivierte Version vom 2011-04-14T13:40:16+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.

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

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

(require-library 'sisc/libs/srfi/srfi-18)
(import srfi-18)


(define x 
  (lambda (n )
    (display n)
    (if (< n 10) (x (+ 1 n)))))

(define mythread
(let ((t (thread-start! (make-thread (lambda () (x 0)  )))))
      (thread-join! t 10)))

(mythread)

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

(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