Sätze und Zusammenhänge

Aus ProgrammingWiki

Archivierte Version vom 2012-04-02T17:59:01+00:00. Aktuelle Version

(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 ()
          (when (> clock 0)
            (set! clock (- clock 1))
            (when (= clock 0) (handler))))))

(define-syntax timed-lambda
  (syntax-rules ()
    ((_ formals exp1 exp2 ...)
     (lambda formals (decrement-timer) exp1 exp2 ...))))

(define-syntax time-ltd-task
  (syntax-rules ()
    ((_ task ticks)
     (let ((in-time #t))
       (start-timer ticks (lambda () (set! in-time #f)))
       (let ((res task))
         (if in-time res "expired"))))))

;;; STREAMS - Implementation mit verzoegerter Evaluation (delay, force)

;; Selektoren

(define stream-car
  (lambda (s)
    (car (force s))))

(define stream-cdr
  (lambda (s)
    (cdr (force s))))

;; Konstruktoren

(define-syntax stream-cons
  (syntax-rules ()
    ((_ x str) (delay (cons x str)))))

(define make-stream 
  (lambda (seed proc)
    (letrec 
        ((stream-builder
          (lambda (n)
            (delay (cons n (stream-builder (proc n)))))))
      (stream-builder seed))))

;; Operationen mit streams

(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)
    (delay
      (cons
       (f (stream-car str))
       (stream-map f (stream-cdr str))))))

(define print-stream
  (lambda (str items)
    (if (<= items 0)
        (begin
          (display "...")(newline))
        (begin
          (write (stream-car str))
          (display ", ")
          (print-stream (stream-cdr str)(- items 1))))))

; nat_zahlen
; (display (stream->list nat_zahlen 20))
; nat_zahlen
; (display (stream->list (stream-map (lambda (i) (* 10 i)) nat_zahlen) 10))

;; ---  Ende streams ---

;;; Aufzaehlbare Mengen 

(define nat_zahlen (make-stream 0 (lambda (n) (+ n 1))))

(define menge-bis print-stream)  ; angepasster Prozedurnamen

(define generiere_aufzaehlbare_menge 
  (lambda (f)
    (stream-map f nat_zahlen)))

(define generiere_aufzaehlbare_wortmenge 
  (lambda (f)
    (stream-map number->string (stream-map f nat_zahlen))))

Aufzählbarkeit und Semi-Entscheidbarkeit

... Zur Implementierung der Ideen dieses Beweises benötigen wir ein Konzept der zeitlich beschränkten Berechnung: Beim Start einer Berechnungsaufgabe wird eine gewisse Anzahl von Ticks angegeben. Ist die betreffende Berechnung in dieser Zeit abgeschlossen, wird deren Ergebis zurück gegeben, anderenfalls "expired".

(time-ltd-task (fib 10) 200)

Verändern Sie die Zahl der Ticks, die zur Berechnung von (fib 10) zur Verfügung stehen, zu 150. Diese Zeit ist zu kurz, um das Ergebnis zu ermitteln.

Man kann das minimal erforderliche Zeitlimit (in Ticks) zur Berechnung von (fib 10) experimentell ermitteln. Bequemer ist der folgende Aufruf, der die gesuchte Anzahl ausgibt. Aufgrund der hier gewählten (unsichtbaren) Implementierung des Timer-Systems sind die Anzahl der erforderlichen Ticks Rechner- und Netz-unabhängig.

(find-minimal-amount-of-time 1)  ; mindestens 1

Im Gegensatz zu dem weiterhebenden Konzept der engines wird der Rest einer Berechnung im Falle nicht ausreichender Zeit nicht aufgehoben. Das ist für unsere Vorhaben hier auch nicht nötig.

Abzählbarkeit und Aufzählbarkeit

Paarungsfunktionen usw.

Entscheidbarkeit und Aufzählbarkeit

Satz: Eine Menge M, mit M\subseteq A^*, ist entscheidbar genau dann, wenn M und A^*\setminus M (Komplementmenge) aufzählbare Menge sind.

Wir wollen den Beweis des Teils "Wenn M und A^*\setminus M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge." mit einem ausführbaren Beispiel illustrieren.

Wir wählen für f die Aufzählprozedur für die ungeraden Zahlen und für g die Aufzählprozedur für die geraden Zahlen. Damit erzeugen wir die betrachteten Mengen M und A^*\setminus M.

(define M (generiere_aufzaehlbare_menge f))
(define A*-M (generiere_aufzaehlbare_menge g))

Von beiden Mengen schauen wir uns jeweils 10 Elemente an.

(menge-bis M 10)
(menge-bis A*-M 10)

Wie man sieht, haben wir es mit Mengen von Zahlwörtern zu tun.

Die Prozedure für \chi_M wurde so konstruiert, wie im Beweis angegeben. Erproben Sie selbst einige Aufrufbeispiele mit selbstgewählten Wörtern aus A^*, also Wörtern natürlicher Zahlen.

(chi_M "9199")

Sätze und Zusammenhänge

Aufzählbarkeit und Semi-Entscheidbarkeit

Abzählbarkeit und Aufzählbarkeit

Entscheidbarkeit und Aufzählbarkeit

Suche