BuK/IIm10/BuK-Übung04 G1

Wiki-Quelltext dieser Seite.

=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.
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
==Lösung==
<code id="4da47a7597a24" hidden>
;###############   wortmenge.ss   ############
;(module wortmenge Racket
;  (provide wortmenge-stufe wortmenge-bis-stufe)

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

;#########################   streams.ss   #######################
;;; STREAMS - Implementation mit verzoegerter Evaluation (delay, force)
;;  als cons aus einem Kopfglied und einem verzögerten Reststream

(module streams Racket
  (provide stream-car stream-cdr stream-cons stream? stream-map print-stream)
  
  ;; Selektoren
  
  (define stream-car car)
  
  (define stream-cdr
    (lambda (stm)
      (force (cdr stm))))
  
  ;; Konstruktoren
  
  (define-syntax stream-cons
    (syntax-rules ()
      ((_ head tail) (cons head (delay tail)))))
  
  ;; Praedikat
  
  (define stream?
    (lambda (stm)
      (and (pair? stm)(promise? (cdr stm)))))
  
  ;; Operationen mit streams
  
  (define make-stream 
    (lambda (seed proc)
      (letrec 
          ((stream-builder
            (lambda (n)
              (stream-cons n (stream-builder (proc n))))))
        (stream-builder seed))))
  
  (define *the-end-of-stream-tag*
    (make-stream
     "eos"
     (lambda (str) str)))
  
  (define stream-item
    (lambda (str k)
      (if (= k 0)
          (stream-car str)
          (stream-item (stream-cdr str) (- k 1)))))
  
  (define stream->list
    (lambda (str n)
      (if (<= n 0)
          '()
          (cons 
           (stream-car str) 
           (stream->list (stream-cdr str) (- n 1))))))
  
  (define stream-map
    (lambda (f str)
      (stream-cons
       (f (stream-car str))
       (stream-map f (stream-cdr str)))))
  
  (define print-stream
    (lambda (stm n)
      (cond
        ((<= n 0) (printf "...~n"))
        (else
         (printf "~s, " (stream-car stm))
         (print-stream (stream-cdr stm) (- n 1))))))
  
  (define stream+
    (lambda (stm1 stm2)
      (stream-cons
       (+ (stream-car stm1) (stream-car stm2))
       (stream+ (stream-cdr stm1) (stream-cdr stm2)))))
  
  )

;;;  Beispiele
;
;(define nat-stream
;  (lambda (start)
;    (stream-cons start (nat-stream (+ start 1)))))
;
;(define natzahlen (nat-stream 0))
;
;(define random-stream
;  (lambda ()
;    (stream-cons (random 101) (random-stream))))
;
;(define fib
;    (lambda (n)
;      (if (< n 2)
;          1
;          (+ (fib (- n 1)) (fib (- n 2))))))
;(define fibstream (stream-map fib natzahlen))

;###########################   engine.ss   ###################################
(module engine mzscheme
  (provide make-engine time-ltd-calc
           (rename timed-apply #%app)
           mileage)
  
  (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)
              (#%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)))))
  
  )
</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>

=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==

=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==