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=
<language>Scheme</language>
==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.
<language>Scheme</language>
==Lösung==
Für den Nachweis muss eine Funktion implementiert werden, die wie folgt definiert ist:
<math>
\chi(w)=\begin{cases}
\#t,\text{wenn }f_M(i)=w\\
\#f,\text{wenn }f_{A^*\backslash M}(i)=w
\end{cases}
</math>
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 id="4da6f40c054f1">
(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 id="4da6f40c057f0">
(gM 12)
</run>
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.
<code id="4da6f40c05573">
(define pseudo_chi-strichM
(lambda (w n)
(cond
((= n 0) #f)
((string=? "" w) (pseudo_chi-strichM w (- n 1)))
(else
(let ((num (- (char->integer (string-ref w (- (string-length w) 1))) 48))) (if (= 0 (modulo num 2)) #t
(pseudo_chi-strichM w (- n 1))))))))
(define pseudo_chi-strichA-M
(lambda (w n)
(cond
((= n 0) #f)
((string=? "" w) (pseudo_chi-strichA-M w (- n 1)))
(else
(let ((num (- (char->integer (string-ref w (- (string-length w) 1))) 48))) (if (= 1 (modulo num 2)) #t
(pseudo_chi-strichA-M w (- n 1))))))))
</code>
<run id="4da6f40c05863">
(pseudo_chi-strichM "12" 100)
;(pseudo_chi-strichM "13" 100)
</run>
<run id="4da6f40c058e8">
;(pseudo_chi-strichA-M "12" 100)
(pseudo_chi-strichA-M "13" 100)
</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. Damit diese Methoden funktionieren muss zunächst die Idee zur Nutzung der zeitbeschränkten Evaluation näher erläutert werden.
Die Idee dazu ist es, jedem Wort aus <math>A^{*}</math> immer mehr Zeit zur Berechnung zu geben. Kann die Zugehörigkeit zur Menge M in einer vorgegebenen Zeit nicht gefunden werden, so wird dieses Wort zurückgestellt und später mit mehr Zeit wieder an Chi-Strich übergeben.
Damit sichergestellt wird, dass jedes Wort immer wieder geprüft wird, verwenden wir eine Vorgehensweise, ähnlich dem Ersten Cantorschen Diagonalargument. Dabei werden alle Wörter aus <math>A^{*}</math> und die Anzahl der Takte zur Berechnung in einer Tabelle der folgenden Form angeordnet:
[[Media:Beispiel.ogg]]
Die Nummern in den Zellen geben dabei eine bijektive Abbildung der Natürlichen Zahlen auf die Kombination aller möglichen Wörter aus <math>A^{*}</math> und der Anzahl der Takte an. Eine Funktion die diese Abbildung berechnet ist <math>z(x,y) = \frac{1}{2}*(x+y)*(x+y+1)+y</math>. Diese müssen wir nun noch nach x bzw. y umstellen.
Dabei erhalten wir: <math>x=\frac{k*(k+3)}{2}-n</math> und <math>n-\frac{k*(k+1)}{2}</math> mit <math>k,x,y >= 0</math>
<code hidden id="4da6f40c055f0">
;(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)))
</code>
<code id="4da6f40c05660">
(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 hidden>
(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 id="4da6f40c056dc">
(define fM
(lambda (n)
(let* ((x-y (z-1 n)) (i (car x-y)) (takte (cdr x-y)) (w_i (gM i)))
(if (pseudo_chi-strichM w_i (+ 10 takte)) 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)))
(if (pseudo_chi-strichA-M w_i (+ 10 takte)) w_i "1"))))
</code>
<run id="4da6f40c059d0">
(fM 6)
</run>
<run id="4da6f40c05a53">
(fA-M 10)
</run>
Damit ist es nun ein leichtes, die Chi-Funktion mit Hilfe von fM(n) und fA-M(n) anzugeben.
<code id="4da6f40c0574d">
(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 id="4da6f40c05acb">
(chi-beweis "13")
</run>