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

;;; 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 (equal? (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>(fib 10)</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) zur Berechnung von <tt>(fib 10)</tt> 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.

<run id="4f79e5b49a638">
(find-minimal-amount-of-time 1)  ; mindestens 1
</run>

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.

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