Berechenbarkeitstheorie/Sätze und Zusammenhänge
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>SchemeJS</language>
<code id="4f7aacbdd2dad" hidden>
;;; CW 2012: Wenn eine Menge M semi-entscheidbar ist, dann ist M aufzaehlbar.
;; Sprache Scheme, Pretty Big
; 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
</code>
<code id="4f7aacbdd2e4a" 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==
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 verwendet. In folgendem Beispiel geben wir 200 Zeiteinheiten vor und versuchen in dieser Zeit die Berechnung der 10. Fibonacci-Zahl abzuschließen.
<run id="4f87e47486b76">(start-timer 200 (lambda () (quit "expired")))
(fib 10)
</run>
Das gelingt offensichtlich.
'''Aufgabe''': Modifizieren Sie die Vorgabezeit solange, dass sie zur Berechnung von <tt>(fib 10)</tt> gerade noch ausreicht.
'''Aufgabe''': Geben Sie der Berechnung von <tt>(fib 40)</tt> wiederum 200 Zeiteinheiten und starten Sie die Berechnung. Klar, die Zeit reicht nicht aus. Wichtig ist nun die Beobachtung, dass die Rechnung wirklich abgebrochen wird. Es würde uns nichts nützen, wenn das Programm sagt, dass die Zeit nicht reicht, der Prozess aber munter fortgesetzt wird.
===Paarungsfunktion===
Der Beweis des o.g. Satzes erfordert die Definition einer Aufzählfunktion $f:\NN\mapsto M$. Zur Berechnung von $f(i)$ wird zuerst aus $i$ genau ein Paar $(x,y)$ ermittelt. Anschließend findet die zeitlich beschränkte Berechnung von $\chi'_M(g(x))$ statt: Ist sie nach $y$ Zeiteinheiten beeandet, liefert $f(i)$ das Ergebnis $g(x)$, wobei $g$ die Aufzählprozedur von $A^*$ ist. Anderenfalls wird die Berechnung abgebrochen.
Erwartungsgemäß muss die Funktion $i\mapsto (x,y)$ bijektiv und berechenbar sein. Diese Eigenschaft besitzen Paarungsfunktionen, wie etwa die von Cantor:
\[i = \pi(x,y) = \frac{(x+y)(x+y+1)}{2}+y \]
<run id="4f83fdde57a01">(pi-cantor 3 1)</run>
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}$.
<run id="4f83fdde57b14">(pi-1x 11)</run>
<run id="4f83fdde57c92">(pi-1y 11)</run>
Mit dem folgenden Aufruf kann man einige der in der Tabelle eingetragenen Werte erzeugen.<br/>
$\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}$
<run id="4f8412b51c1a4">(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))</run>
Das Format der ausgegebenen Listenelemente ist: <tt>((x y) i)</tt>.
Für ein konkretes Beispiel benötigen wir ein Alphabet $A$ (Variable <tt>alphabet</tt>):
<code id="4f82aa6a81d56">(define alphabet '(a b c))</code>
<code id="4f82ace00e50a" hidden>
(define n (length alphabet))
</code>
Die Aufzählfunktion $g:\NN\setminus\{0\}\mapsto A^*$ wird durch die Prozedur <tt>zahl->wort</tt> berechnet.
Für die Umkehrfunktion $g^{-1}: A^*\mapsto \NN\setminus\{0\}$ haben wir die Prozedur <tt>wort->zahl</tt>.
An welcher Position in der Menge $A^*$ befindet sich das Wort <tt>cac</tt>?
<run id="4f82aa6a81e97">(wort->zahl "cac")</run>
Welches Wort steht an Position 34?
<run id="4f830935f2c80">(zahl->wort 34)</run>
'''Aufgabe''': Verändern Sie die oben eingegebenen Argumente und überprüfen Sie das jeweilige Ergebnis durch die entsprechende Umkehrfunktion.
Jetzt haben wir alle Vorbereitungen getroffen, um den Beweis an einem Beispiel zu illustrieren. $M$ sei die Menge aller Wörter aus $A^*$, die eine Fibonacci-zahlige Anzahl von b's enthalten.
<run id="4f87edda05996">(g 38726)</run>
Wir erhalten ein Wort, das 5 b's enthält. 5 ist eine Fibonacci-Zahl. Also gehört dieses Wort zu $M$.
$\chi'_M$ muss also für $i=0,1,\ldots$ prüfen, ob $fib(i)=k$, wobei $k$ die Anzahl der im betrachteten Wort vorkommenden b's bezeichnet. Für $k=5$ erkennt $\chi'_M$ die Übereinstimmung bei $i=5$ und liefert den Wert $wahr$.
40 Zeiteinheiten reichen für diese Berechnung jedoch nicht aus:
<run id="4f87edda05ff3">(f (pi-cantor 38726 40))</run>
Das Ergebnis ist ein Wort, das zu $M$ gehört, nämlich "b".
'''Aufgabe''': Erhöhen Sie die Zeitvorgabe um 1 auf 41 und kommentieren Sie das Ergebnis.
Wir wählen nun ein Beispielwort aus $A^*$ das 6 b's enthält.
<run id="4f87edda064b5">(g 116178)</run>
Es gehört nicht zu $M$. Ganz gleich wie viel Zeit wird zur Berechnung von $f$ zur Verfügung stellen, es gibt kein anderes Ergebnis als "b".
<run id="4f87edda0656d">(f (pi-cantor 116178 10000000))</run>
==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'' Mengen 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 Prozedur 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>