Berechenbarkeitstheorie/Sätze und Zusammenhänge
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
<code id="4f7aacbdd2dad" hidden>
;;; Simple timer interrupt system
; It runs with both Scheme an Racket as well.
; Source 'Engines from Continuations' (R. Kent Dybvig and Robert Hieb) adapted for computability purposes by CW, 2012
(define start-timer #f)
(define stop-timer #f)
(define decrement-timer #f)
(define quit #f) ; nonlocal exit, as used in the definition of timed-lambda
(define gen-quit
(lambda ()
(equal? "expired" ; don't change "expired" here
(call/cc
(lambda (cont)
(set! quit cont))))))
(begin (gen-quit) (void))
(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)
(begin
(start-timer ticks (lambda () (quit "expired")))
task))))
;;; 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)))))
</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==
===Zeitbeschränkte Berechnung===
Zur Implementierung der zentralen Ideen dieses Beweises benötigen wir das Konzept ''zeitbeschränkter Berechnung'': Beim Start einer Berechnungsaufgabe wird eine gewisse Anzahl von Ticks angegeben. Ist die betreffende Berechnung in dieser Zeit abgeschlossen, wird deren Ergebis zurückgegeben. Anderenfalls bricht die Berechnung ab. Zur Information erscheint die Ausschrift '#!void' (allerdings nicht als auswertbarer Rückgabewert).
<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)
(time-ltd-task (fib 10) ticks)
(display ticks)(display " ")
(find-minimal-amount-of-time (- ticks 1))))
</code>
<run id="4f79e5b49a5b4">
(time-ltd-task (fib 10) 200)
</run>
'''Aufgabe''': Verändern Sie die Zahl der Ticks für die Berechnung von <tt>(fib 10)</tt> und versuchen Sie die Zeit herauszufinden, die zur Berechnung von <tt>(fib 10)</tt> 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 <tt>(fib 10)</tt> entsprechend ersetzt.
<code id="4f7aacbdd2edc">
(define find-minimal-amount-of-time
(lambda (ticks)
(time-ltd-task (fib 10) ticks)
(display ticks)(display " ")
(find-minimal-amount-of-time (- ticks 1))))
</code>
<run id="4f7aacbdd2fa7">
(find-minimal-amount-of-time 200)
</run>
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 <tt>fib</tt>, z.B. <tt>(fib 30)</tt>, unter Vorgabe von lediglich 200 Ticks. Beachten Sie, dass eine Berechnung, für die die vorgegebene Zeit nicht ausreicht, automatisch abgebrochen wird.
<run id="4f7aaeb9c37ae">
(time-ltd-task (fib 30) 200)
</run>
===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 \]
<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>.
==Abzählbarkeit und Aufzählbarkeit==
<code id="4f82aa6a81d56">(define alphabet '(a b c))</code>
<code id="4f82ace00e50a" hidden>
;;; Aufbauschema Wortmenge
;; Bijektive Abbildung:
;; wort->zahl: A* -> N
(define alphabet '(a b c))
(define n (length alphabet))
(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))))
(define potenz
(lambda (basis exponent)
(if (= exponent 0)
1
(* basis (potenz basis (- exponent 1))))))
(define wort->zahl
(lambda (wort)
(let ((m (string-length wort)))
(+ (/ (- (potenz n m) 1) (- n 1)) (position wort)))))
(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)))))))))
;; Umkehrung: zu einer geg. nat. Zahl soll das zugehörige Wort aus A* ausgegeben werden
;; zahl->wort: N -> A*
;(define woerter-mit-laenge-variante
; (lambda (lng)
; (if (= lng 0)
; '("")
; (apply
; append
; (map
; (lambda (zeichen)
; (map
; (lambda (w) (string-append w (symbol->string zeichen)))
; (woerter-mit-laenge-variante (- lng 1))))
; alphabet)))))
(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-nr (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
</code>
=== Aufbauschema der Wortmenge ===
$g: A^*\mapsto \NN\setminus\{0\}$ wird durch die Prozedure <tt>wort->zahl</tt> berechnet.
$g^{-1}: \NN\setminus\{0\}\mapsto A^*$ wird durch die Prozedure <tt>zahl->wort</tt> berechnet.
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>
Ü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).
<run id="4f830cbf6cc14">(llo? "abcaca" "bacac")</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'' 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>