Sätze und Zusammenhänge

Aus ProgrammingWiki

Archivierte Version vom 2012-04-13T08:31:50+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Aufzählbarkeit und Semi-Entscheidbarkeit
- 1.1 Zeitbeschränkte Berechnung
- 1.2 Paarungsfunktion
2 Abzählbarkeit und Aufzählbarkeit
- 2.1 Aufbauschema der Wortmenge
- 2.2 Längenlexikografische Ordnung
3 Entscheidbarkeit und Aufzählbarkeit

;;; CW 2012: Wenn eine Menge M semi-entscheidbar ist, dann ist M aufzaehlbar.

;; Sprache Scheme, Pretty Big
;; #lang racket  ; call/cc ist in Racket etwas anderes definiert. --> Ausgaben doppelt

; Source 'Engines from Continuations' (R. Kent Dybvig and Robert Hieb) adapted for computability lessons by CW, 2012

(define start-timer #f)
(define state-timer #f)
(define stop-timer #f)
(define decrement-timer #f)

(define quit #f)  ; Continuation zum Ausstieg aus einer Berechnung
(call/cc (lambda (cont) (set! quit cont)))  ; Kontrolle geht an console

(let ([clock 0] [handler #f])
  (set! start-timer
        (lambda (ticks new-handler)
          (set! handler new-handler)
          (set! clock ticks)))
  (set! state-timer 
        (lambda ()
          clock))
  (set! stop-timer
        (lambda ()
          (let ([time-left clock])
            (set! clock 0)
            time-left)))
  (set! decrement-timer
        (lambda ()    ; (printf "~a " (state-timer))
          (when (> clock 0)
            (set! clock (- clock 1))
            (when (= clock 0) (handler))))))


; ----------  Einfache Anwendung des Timer-systems ----

(define fib
  (lambda (n)  
    (decrement-timer)  ; Timer wird decrementiert
    (cond
      ((= n 0) 0)
      ((= n 1) 1)
      (else
       (+ (fib (- n 1)) (fib (- n 2)))))))

;> (start-timer 200 (lambda () (quit "expired")))
;> (state-timer)
;200
;> (fib 10)
;55

; Erforderliche Berechnungszeit für (fib 10): 200 - 23 = 177
;> (state-timer)
;23
;> (fib 10)
;"expired"
;> (start-timer 178 (lambda () (quit "expired")))
;> (fib 10)
;55
;> (state-timer)
;1

; -------------------------------------------------------------

;;; Cantorsche Paarungsfunktion

(define pi-cantor
  (lambda (x y)
    (+ (/ (* (+ x y) (+ x y 1)) 2) y)))

; Umkehrfunktionen 

(define pi-1x
  (lambda (i)
    (let* ((w (floor (/ (- (sqrt (+ (* 8 i) 1)) 1) 2)))
           (t (/ (* w (+ w 1)) 2))
           (y (- i t)))
      (inexact->exact (- w y)))))

(define pi-1y
  (lambda (i)
    (let* ((w (floor (/ (- (sqrt (+ (* 8 i) 1)) 1) 2)))
           (t (/ (* w (+ w 1)) 2)))
      (inexact->exact (- i t)))))

;; Aufruf liefert eine Listendarstellung fuer die pi-Tabelle (s. Vorlesung)
;  Listenelemente: ((x y) z)
;> (map (lambda (i) (list (list (pi-1x i)(pi-1y i)) i)) '(0 1 2 3 4 5 6 7 8 9 10 11 12 13))
;(((0 0) 0) ((1 0) 1) ((0 1) 2) ((2 0) 3) ((1 1) 4) ((0 2) 5) ((3 0) 6) ((2 1) 7) ((1 2) 8) ((0 3) 9) ((4 0) 10) ((3 1) 11) ((2 2) 12) ((1 3) 13))

; --------------------------------------------------------------------------------

;;; Aufbauschema Wortmenge

;; Wahl eines Alphabets (Liste mit Scheme-Symbolen)

(define alphabet '(a b c))
(define n (length alphabet))

;; Bijektive Funktion wort->zahl: A* -> N\{0}  

; Wert eines Alphabetzeichen = dessen Positionsnummer, sonst 0

(define wert
  (lambda (zeichen)
    (letrec
        ((helper
          (lambda (alph i)
            (cond 
              ((null? alph) 0)
              ((eq? zeichen (car alph)) i)
              (else
               (helper (cdr alph) (+ i 1)))))))
      (helper alphabet 1))))

;> (wert 'b)
;2

(define potenz
  (lambda (basis exponent)
    (if (= exponent 0)
        1
        (* basis (potenz basis (- exponent 1))))))

;; Position des entspr. Wortes w, mit |w|=k, innerhalb der zugehör. Menge aller Worter der Laenge k.

(define position
  (lambda (wort)
    (cond
      ((= (string-length wort) 0) 1)
      ((= (string-length wort) 1) (wert (string->symbol (string (string-ref wort 0)))))
      (else
       (+ (* n (- (position (substring wort 0 (- (string-length wort) 1))) 1)) 
          (wert (string->symbol (substring wort (- (string-length wort) 1) (string-length wort)))))))))

;> (position "ba")
;4

(define wort->zahl
  (lambda (wort)
    (let ((m (string-length wort)))
      (+ (/ (- (potenz n m) 1) (- n 1)) (position wort)))))

;> (wort->zahl "ba")
;8

;;  Umkehrung: zu einer geg. nat. Zahl soll das zugehörige Wort aus A* ausgegeben werden

;;  zahl->wort: N\{0} -> A*  

(define woerter-mit-laenge
  (lambda (lng)
    (if (= lng 0)
        '("")
        (apply
         append
         (map 
          (lambda (w) 
            (map
             (lambda (zeichen)
               (string-append w (symbol->string zeichen)))
             alphabet))
          (woerter-mit-laenge (- lng 1)))))))

;> (map wort->zahl (woerter-mit-laenge 3))
;(14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40)

(define zahl->wort
  (lambda (n)
    (letrec
        ((suche-n
          (lambda (n ls)
            (cond
              ((null? ls) #f)
              ((= n (wort->zahl (car ls))) (car ls))
              (else 
               (suche-n n (cdr ls))))))
         (helfer
          (lambda (i)
            (let ((resultat (suche-n n (woerter-mit-laenge i))))
              (if resultat
                  resultat
                  (helfer (+ i 1)))))))
      (helfer 0))))

;> (map zahl->wort '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16))
;("" "a" "b" "c" "aa" "ab" "ac" "ba" "bb" "bc" "ca" "cb" "cc" "aaa" "aab" "aac")

;;; Laengenlexikografische Ordnung

(define llo?
  (lambda (w1 w2)
    (< (wort->zahl w1) (wort->zahl w2))))

;> (llo? "bacac" "bacacc")
;#t 

; ---------------------------------------------------------------------------

;; M: Wörter über {a,b,c}, die k 'b's enthalten und k ist eine Fibonacci-Zahl

;; g: N->A* ist eine Aufzaehlprozedur fuer A*
;  verwendet zahl->wort, d.h. g liegt ein Aufbauschema fuer A* zugrunde

(define g 
  (lambda (i)
    (if (= i 0)
        ""
        (zahl->wort i))))

;> (g 501502)
;"baccccbacbcc"

;; f: N->M, M ist Teilmenge von A*
;  f startet den Timer mit y Ticks

(define f
  (lambda (i)
    (let* ((x (pi-1x i))(y (pi-1y i))(w-x (g x)))
      (start-timer y (lambda () (quit "b")))
      (if (chi-strich-m w-x)
          w-x
          'dummy))))

;> (f 125802534103)

;; Semi-charakteristische Funktion
;  M ... Woerter aus A* mit Fibonacci-zahligen Vorkommen des alphabetzeichens b
;  Dekrementierung des Timers findet in chi' und in fib statt.

(define chi-strich-m
  (lambda (w)
    (letrec
        ((helfer
          (lambda (i)   ; (printf "~a " i)
            (decrement-timer)
            (if (= (symbol-vorkommen w 'b) (fib i))
                #t
                (helfer (+ i 1))))))
      (helfer 0))))

;; symbol-vorkommen bestimmt die Anzahl der Vorkommen eines bestimmten 
;  Alphabetzeichens (symbol) in einem bestimmten Wort

(define symbol-vorkommen
  (lambda (w sym)
    (letrec
        ((helper
          (lambda (char-ls char)
            (cond
              ((null? char-ls) 0)
              ((char=? (car char-ls) char)(+ 1 (helper (cdr char-ls) char)))
              (else
               (helper (cdr char-ls) char))))))
      (helper (string->list w) (string-ref (symbol->string sym) 0)))))

;> (symbol-vorkommen "abababa" 'b)
;3
;> (g 501502)
;"baccccbacbcc"
;> (symbol-vorkommen (g 501502) 'c)
;7

Aufzählbarkeit und Semi-Entscheidbarkeit

Es geht hier um den Beweis des Satzes: Wenn eine Menge M semi-entscheidbar ist, dann ist M auch aufzählbar.

Da die Semi-Entscheidbarkeit mittels semi-charakteristischer Funktion \chi'_M behandelt wird, müssen wir damit rechnen, dass \chi'_M für gewisse Wörter w nicht definiert ist. Die zugehörige Prozedur würde ewig laufen und kein Ergebnis zurückgeben. Dies führt uns zu der Idee, Berechnungen zeitlich zu beschränken.

Zeitbeschränkte Berechnung

Hierfür wird ein Timer gestartet.

(start-timer 200 (lambda () (quit "expired")))

Er stellt einer zeitbeschränkten Berechnung 200 Zeiteinheiten (Ticks) zur Verfügung.

Diese Zeit reicht aus, um die 10. Fibonacci-Zahl zu berechnen:

(fib 10)

Ein Teil der 200 Ticks ist dabei verbraucht worden.

(state-timer)

Wenn wir die gleiche Berechnung nochmals durchführen, reicht die Zeit nicht aus. Die aktuelle Berechnung wird abgebrochen.

(fib 10)

Noch deutlicher wird das bei einer sehr aufwändigen Berechnung, wie (fib 40). Es würde viele Stunden brauchen, um ein Ergebnis zu erzeugen. Uns reicht es also nicht zu erfahren, dass eine Rechnung in einer bestimmten Zeit nicht beendet werden konnte, während der Rechenprozess munter weiterläuft. Die Rechnung muss abgebrochen werden.

(start-timer 200 (lambda () (quit "expired")))
(fib 40)

Wie wir an diesem Beispiel gut sehen konnten, ist das der Fall.

Aufgabe: Verändern Sie die Zahl der Ticks für die Berechnung von (fib 10) und versuchen Sie die Zeit herauszufinden, die zur Berechnung von (fib 10) mindestens benötigt wird.

Aufgabe: Zur Überprüfung Ihres experimentell ermittelten Resultats verwenden Sie die folgende Prozedur. Sie kann leicht für andere Anwendungen angepasst werden, indem man den (fib 10) entsprechend ersetzt.

Aufgrund der hier gewählten (unsichtbaren) Implementierung des Timer-Systems ist die Anzahl der erforderlichen Ticks Rechner- und Netz-unabhängig.

Aufgabe: Experimentieren Sie mit größeren Argumenten für fib, z.B. (fib 30), unter Vorgabe von lediglich 200 Ticks. Beachten Sie, dass eine Berechnung, für die die vorgegebene Zeit nicht ausreicht, automatisch abgebrochen wird.

Paarungsfunktion

Der programmtechnisch unproblematische Abbruch einer Berechnung bei Überschreitung einer vorgegebenen Zeit ist eine wichtige Eigenschaft, die wir im Folg. bei der Implementierung der Aufzählfunktion ausnützen werden.

Wir verwenden die Cantorsche Paarungsfunktion:

i = \pi(x,y) = \frac{(x+y)(x+y+1)}{2}+y

(pi-cantor 3 1)

Die Vorschriften zur Ermittlung von x und y lauten: y=i-t und x=w-y, wobei w=\left\lfloor\frac{\sqrt{8i+1}-1}{2}\right\rfloor und t=\frac{w(w+1)}{2}.

(pi-1x 11)

(pi-1y 11)

Mit dem folgenden Aufruf kann man einige der in der Tabelle eingetragenen Werte erzeugen.
$\begin{array}{c|cccccc}

  x\backslash y & 0 & 1 & 2 & 3 & 4 & \dots\\\hline
 0  & 0 & 2 & 5 & 9 & 14 & \dots \\
 1  & 1 & 4 & 8 & 13 & \dots &   \\
 2  & 3 & 7 & 12 & \dots &   &   \\
 3  & 6 & 11 & \dots &   &  &  \\
 4  & 10 & \vdots & \vdots & \vdots & \vdots &

\end{array}$

(map (lambda (i) (list (list (pi-1x i)(pi-1y i)) i)) '(0 1 2 3 4 5 6 7 8 9 10 11 12 13))

Das Format der ausgegebenen Listenelemente ist: ((x y) i).

Abzählbarkeit und Aufzählbarkeit

(define alphabet '(a b c))

Aufbauschema der Wortmenge

g: A^*\mapsto \NN\setminus\{0\} wird durch die Prozedure wort->zahl berechnet.

g^{-1}: \NN\setminus\{0\}\mapsto A^* wird durch die Prozedure zahl->wort berechnet.

An welcher Position in der Menge A^* befindet sich das Wort cac?

(wort->zahl "cac")

Welches Wort steht an Position 34?

(zahl->wort 34)

ÜA: Verändern Sie die oben eingegebenen Argumente und überprüfen Sie das jeweilige Ergebnis durch die entsprechende Umkehrfunktion.

Längenlexikografische Ordnung

Zur Definition der (zweistelligen) längenlexikografischen Ordnung ist es lediglich notwendig, die jeweils zugehörigen natürlichen Zahlen miteinander zu vergleichen (Kleinerrelation).

(llo? "abcaca" "bacac")

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

Inhaltsverzeichnis

Aufzählbarkeit und Semi-Entscheidbarkeit

Zeitbeschränkte Berechnung

Paarungsfunktion

Abzählbarkeit und Aufzählbarkeit

Aufbauschema der Wortmenge

Längenlexikografische Ordnung

Entscheidbarkeit und Aufzählbarkeit

Suche