Berechenbarkeitstheorie/Sätze und Zusammenhänge

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<code id="4f79e5b49a28a" 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 ()
          (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"))))))
</code>

<code id="4f79e5b49a31c" hidden>
;;; 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==

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

<code id="4f79e5b49a3a6" hidden>
(define fib
  (timed-lambda (n)  ; note the timed-lambda definition for decrement-timer invocations
    (cond
      ((= n 0) 0)
      ((= n 1) 1)
      (else
       (+ (fib (- n 1)) (fib (- n 2)))))))

(define find-minimal-amount-of-time
  (lambda (ticks)
    (if (eq? (time-ltd-task (fib 10) ticks) "expired")
        (find-minimal-amount-of-time (+ ticks 1))
        ticks)))
</code>

<run id="4f79e5b49a5b4">
(time-ltd-task (fib 10) 200)
</run>

Verändern Sie die Zahl der Ticks, die zur Berechnung von <tt></tt> zur Verfügung stehen, zu 150. Diese Zeit ist zu kurz, um das Ergebnis zu ermitteln. 

Man kann das minimal erforderliche Zeitlimit (in Ticks) experimentell ermitteln. Man kann auch den folgenden Aufruf dafür verwenden.

<run id="4f79e5b49a638">
(find-minimal-amount-of-time 1)  ; the minimal value of ticks is 1
</run>


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