Berechenbarkeitstheorie/Sätze und Zusammenhänge

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<code id="4f79c91d61e65" hidden>

;;; Timer interrupt system

(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 ...))))
</code>

<code id="4f79c91d61ed7">
(define fib
  (timed-lambda (n)
    (cond
      ((= n 0) 0)
      ((= n 1) 1)
      (else
       (+ (fib (- n 1)) (fib (- n 2)))))))
</code>

<run id="4f79c91d61f5c">
(start-timer 7 (lambda () 'Hallo))
(fib 10)
</run>


;;; 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))))
</code>

==Aufzählbarkeit und Semi-Entscheidbarkeit==


==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.

<code id="4f7842e667e5b" hidden>
(define f 
  (lambda (n)
    (number->string (+ (* 2 n) 1))))

(define g 
  (lambda (n)
    (number->string (* 2 n))))

(define chi_M               
  (lambda (w)
    (letrec
        ((helper
          (lambda (i)
            (cond
              ((string=? (f i) w) #t)
              ((string=? (g i) w) #f)
              (else
               (helper (+ i 1)))))))
      (helper 0))))
</code>

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$.

<code id="4f7842e667ec5">
(define M (generiere_aufzaehlbare_menge f))
(define A*-M (generiere_aufzaehlbare_menge g))
</code>

Von beiden Mengen schauen wir uns jeweils 10 Elemente an.

<run id="4f7842e667f39">
(menge-bis M 10)
(menge-bis A*-M 10)
</run>

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. 

<run id="4f7842e667f93">
(chi_M "9199")
</run>