BuK/IIm10/BuK-Übung04 G1
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
=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==
<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>
(import threading)
(define mythread
(let ((t (thread/new (lambda () (expnt 2 10000000)))))
(thread/start t)
(check t 10)))
(define check
(lambda (t n)
(cond
((= 0 n) (thread/interrupt t))
(else (check t (- n 1))))))
</code>
<run>
(mythread)
</run>
<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))))
(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)))))
</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>