Aus ProgrammingWiki

Inhaltsverzeichnis 1 Beweis 1.1 Aufgabenstellung 1.2 Lösung 2 Entscheidbarkeit endlicher Mengen 2.1 Aufgabenstellung 2.2 Lösung 3 Aufzählbarkeit 3.1 Aufgabenstellung 3.2 Lösung 4 Semientscheidbarkeit 4.1 Aufgabenstellung 4.2 Lösung

Beweis

Aufgabenstellung

Zeigen Sie, dass für ein beliebiges Alphabet eine überabzählbar unendliche Menge ist.

Lösung

Um nachzuweisen, dass eine Menge abzählbar unendlich ist, muss eine bijektive Abbildung auf die natürlichen Zahlen möglich sein.

Für die Wortmenge wurde in der letzten Übung nachgewiesen, dass eine Abbildung möglich ist, die Wortmenge über einem Alphabet also abzählbar unendlich ist.

Um nachzuweisen, dass abzählbar unendlich ist, müsste man also auch auf die natürlichen Zahlen abbilden können. Da diese Abbildung bei der Wortmenge schon funktioniert hat, kann man auch eine Abbildung von auf erzeugen um eine Abzählbarkeit nachzuweisen.

Bei handelt es sich jedoch um die Potenzmenge von . Laut dem Satz von Cantor gilt für unendliche Mengen: .

(vgl.Die Größe der Potenzmenge (Kardinalität))

Da also in der Wortmenge weniger Elemente vorhanden sind als in der Potenzmenge ist keine bijektive Abbildung möglich.

Entscheidbarkeit endlicher Mengen

Aufgabenstellung

Implementieren Sie eine Scheme-Prozedur , die eine natürliche Zahl n und eine Liste L nimmt und entweder oder zurück gibt, je nachdem ob oder gilt. Stellen Sie für den Entwurf von die erforderlichen Hilfsprozeduren bereit.

Lösung

(define chi-endlich (lambda (n l) (if (null? l) #f (if (= (car l) n) #t (chi-endlich n (cdr l))))))

(chi-endlich 5 '(7 2 8 2 1 9 5))

ausführen

(chi-endlich 5 '(7 2 8 2 1 9 0))

ausführen

Aufzählbarkeit

Aufgabenstellung

Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen aufzählt.

Lösung

;;; STREAMS - Implementation mit verzoegerter Evaluation (delay, force) ;; als cons aus einem Kopfglied und einem verz�gerten Reststream ;; 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) (display "...\n")) (else (display (stream-car stm)) (display ", ") (print-stream (stream-cdr stm) (- n 1)))))) ;(define print-stream ; ; (lambda (stm n) ; (cond ; ((<= n 0) (display "... \n")) ; (else ; (display (stream-car stm)) ; (display ", ") ; (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))

(define quadrat (lambda (n) (* n n))) (define quadratstream (stream-map quadrat natzahlen))

(print-stream quadratstream 20)

ausführen

Semientscheidbarkeit

Aufgabenstellung

Schreiben Sie eine Scheme-Prozedur, die die Menge der Quadratzahlen relativ zur Menge der natürlichen Zahlen semi-entscheidet.

Hinweis: Implementieren Sie eine Prozedur für die (allgemeingültige) und wenden Sie sie auf die Menge (stream) der natürlichen Zahlen an. Überlegen Sie sich vor dem Aufruf genau, welche Ausgabe Sie erwarten.

Lösung

(define semi (lambda (n) (cond ((chi-endlich n (stream->list quadratstream (+ n 1)))#t) (else (semi n)))))

(semi 5)

ausführen

(define str (stream-map (lambda (x) (* x x)) natzahlen)) (define chi-strich (lambda (w) (letrec ((suche (lambda (menge) (if (= w (stream-car menge)) #t (suche (stream-cdr menge)))))) (suche str))))

(chi-strich 25)

ausführen