Aus ProgrammingWiki

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

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

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

(chi-strich? "aaa")

ausführen

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

(chi-strich? "aaa1")

ausführen

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

ausführen

(f_von_M 10)

ausführen

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:

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)

ausführen

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

(pseudo_chi-strichM "12" 100) ;(pseudo_chi-strichM "13" 100)

ausführen

;(pseudo_chi-strichA-M "12" 100) (pseudo_chi-strichA-M "13" 100)

ausführen

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 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 und die Anzahl der Takte zur Berechnung in einer Tabelle der folgenden Form angeordnet:

Dabei stehen in den Zeilen die Wortnummern aus und in den Spalten die Anzahl der Takte, die maximal zur Berechnung verwendet werden dürfen. Die Nummern in den Zellen geben dabei eine bijektive Abbildung der Natürlichen Zahlen auf die Kombination aller möglichen Wörter aus und der Anzahl der Takte an. Eine Funktion die diese Abbildung berechnet ist . Diese müssen wir nun noch nach x bzw. y umstellen. Dabei erhalten wir: und mit

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

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

(fM 6)

ausführen

(fA-M 10)

ausführen

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

ausführen