uebung3

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Theorie
2 Übungsaufgaben zur Entscheidbarkeit und Aufzählbarkeit

Theorie

Im Gegensatz zu Funktionen sind Mengen nicht berechenbar, sondern entscheidbar. Man spricht bei Mengen von Entscheidbarkeit

relativ entscheidbare Mengen

Eine Menge M_1 ist relativ entscheidbar zur Menge M_2 (M_1,M_2\subseteq A^*), wenn die charakteristische Funktion \chi_{M_1,M_2} mit

\chi_{M_1,M_2}(w)=\begin{cases}wahr & \text{,wenn } w\in M_1\\falsch & \text{, wenn } w\in M_2\setminus M_1\end{cases}

eine totale und berechenbare (kurz: total berechenbar) Funktion ist. D.h. man kann für jedes Element der Menge M_2 sagen, ob es sich um ein Element der Menge M_1 handelt oder nicht.

(absolut) entscheidbare Mengen

Eine Menge M\subseteq A^* ist (absolut) entscheidbar, wenn M zu A^* relativ entscheidbar ist, d.h. wenn \chi_{M,A^*}, kurz \chi_{M}, mit

\chi_{M}(w)=\begin{cases}wahr & \text{,wenn } w\in M\\falsch & \text{, wenn } w\in A^*\setminus M\end{cases}

eine total berechenbare Funktion ist.

Anders gesagt: M ist entscheidbar, wenn es eine Prozedur (eine in einer beliebigen Programmiersprache implementierte Funktion) chi gibt, die für jedes Wort w aus A^* nach endlicher Zeit stoppt und entweder #t (w\in M) oder #f (w \not\in M) ausgibt.

 &gt; (chi "bin_in_M")
 #t
 &gt; (chi "bin_nicht_in_M")
 #f

Aufzählbar

Eine Menge M\subseteq A^* heißt (rekursiv) aufzählbar, wenn es entweder eine total berechbare surjektive Funktion f\colon\N\mapsto M gibt, oder es gilt M = \emptyset. Man nennt f eine Aufzählprozedur oder ein Aufzählverfahren von M.

Stark vereinfacht: aufzählbar = abzählbar + berechenbar

von Aufzählbar zu Entscheidbar

Im allgemeinen Fall sichert die Aufzählbarkeit einer Menge lediglich deren Semi-Entscheidbarkeit.

Eine Menge M\subseteq A^* ist semi-entscheidbar, wenn die partielle (semi-charakteristische) Funktion \chi'_M \colon A^*\mapsto\{\text{wahr}\} mit

\chi'_M(w)=\begin{cases}wahr & \text{, wenn }w\in M\\\perp & \text{, sonst}\end{cases}

berechenbar ist.

Übungsaufgaben zur Entscheidbarkeit und Aufzählbarkeit

Aufgabe 1 (Deutschmann, Horbach)

Wie viele berechenbare charakteristische Funktionen gibt es?

Hinweis: Potenzmenge unendlicher Mengen

\mathscr{P}(A^*) besitzt überabzählbar unendlich viele Mengen

Die Teilmengen von A^* sind selbst endlich oder abzählbar unendlich.

Deshalb gibt es überabzählbar unendlich viele charakteristische Funktionen \chi_M.

Aufgabe 2

Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion (ProgrammingWiki).

Beispiel 1: endliche Menge

A^*=\{a,b\}^* und M\subset A^*=\{w | w\in A^* \text{und } \left|w\right|=3\}

(define 
    endlicheMenge (list 'aaa 'aab 'aba 'abb 'baa 'bab 'bba 'bbb))

(define inList
    (lambda (wrd lst)
        (cond
            [(eq? (car lst) wrd) #t]
            [(not (null? (cdr lst))) (inList wrd (cdr lst))]
            [else #f]))
)

(car endlicheMenge)

Beispiel 2: abzählbar unendliche Menge

M ist die Menge aller Wörter, die aus beliebig vielen a's und b's bestehen und mit a beginnen.

A^*=\{a,b\}^* und M\subset A^*=\{w=aw'| w'\in A^*\}

(define istWortInAlphabet
    (lambda (wrd)
        (cond
            [(string=? (string (car (string->list wrd))) "a") #t]
            [else #f])))

(istWortInAlphabet "aaabb")

Aufgabe 3 (Deutschmann, Horbach)

Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

Wdh: Aufzählbar = abzählbar + berechenbar

abzählbar: Für die Menge der geraden Zahlen G gilt: G\subset\Z, die abzählbar unendlich sind Beweis

berechenbar: Es existiert ein Algorithmus, der für die Funktion f(x) für jedes x \in D_f den zugehörigen Funktionswert f(x) ermittelt

f(x)=\begin{cases}-i & \text{, wenn i gerade}\\i+1 & \text{, wenn i ungerade}\end{cases}

(define gibGeradeZahl
    (lambda (x)
        (cond
            [(= (modulo x 2) 0) (* -1 x)]
            [else (+ x 1)])))

(gibGeradeZahl 4)

Aufgabe 4

Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.

Primzahlen sind abzählbar unendlich Beweis.

Aufzählbar = abzählbar + berechenbar

Aufzählbar:

es gibt eine Aufzählprozedur h:\N\mapsto A^*
total berechenbar
mind. surjektiv

Berechenbar = "Es existiert eine implementierte Funktion (also eine Prozedur)"

Für die Aufzählbarkeit fehlt noch ein Algorithmus für eine Funktion, welche die Primzahlen berechnen kann.

(define kleinster-teiler
  (lambda (n) 
    ;finde a, sodass gilt: a^n mod n = a
    (finde-teiler 2 n)
  )
)
(define finde-teiler
  (lambda (a n)
    ;teile n durch a, wobei 2 < a < sqrt(n)
    (cond ((> (sqrt a) n) n)
          ((teilt? a n) a)
          (else (finde-teiler (+ a 1) n))
    )
  )
)
(define teilt?
  (lambda (a b)
    (= (modulo b a) 0 )
  )
)
(define prime?
  (lambda (n)
    (= (kleinster-teiler n) n)
  )
)


(define f
    (lambda (x) 
        (cond 
            [(prime? x) x]
            [else 2])))


(define primeStream (stream-map natstream f))

(print-stream primeStream 30)

Aufgabe 5

Wir wissen, dass A^* eine abzählbar unendliche Menge ist. Zeigen Sie, dass A^* auch aufzählbar ist.

Hinweis: Hierzu ist es notwendig ein Aufbauschema für A^* zu entwerfen und anschließend eine Prozedur dafür zu implementieren.

(define pow
  (lambda (number exp)
    (if (= exp 0)
      1
      (* number (pow number (- exp 1))))))

(define getElement
  (lambda (set index)
    (if (= index 1)
      (car set)
      (getElement (cdr set) (- index 1)))))
      
(define cardinalNumber
  (lambda (set)
    (if (null? set)
      0
      (+ 1 (cardinalNumber (cdr set))))))


      
(define calculateWordSize
  (lambda (set index)
    (letrec ((calculateWordSizeReal
      (lambda (cardinalNumber index sum exp)
        (if (>= sum index)
          0
          (+ 1 
            (calculateWordSizeReal
              cardinalNumber
              index
              (+ sum (pow cardinalNumber exp))
              (+ 1 exp)))))))
  (calculateWordSizeReal (cardinalNumber set) index 0 1))))

;Berechnet die Anzahl der Wörter mit Länge <= letterCount
(define numberOfWords
  (lambda (cardinalNumber letterCount)
    (if (= letterCount 0)
      0
      (+
        (pow cardinalNumber letterCount)
        (numberOfWords cardinalNumber (- letterCount 1))))))
    
(define createWord
  (lambda (set wordnumber cardinalNumber lettersRemaining)
    (if (= 0 lettersRemaining)
      ""
      (let ((sectionSize (pow cardinalNumber (- lettersRemaining 1))))
        (let ((rest (modulo wordnumber sectionSize))
            (result (quotient wordnumber sectionSize)))
          (if (= 0 rest)
            (string-append
              (string (getElement set result))
              (createWord set sectionSize cardinalNumber (- lettersRemaining 1)))
            (string-append
              (string (getElement set (+ result 1)))
              (createWord set rest cardinalNumber (- lettersRemaining 1)))))))))
                
(define fCreator
  (lambda (set)
    (lambda (index)
      (if (= index 0)
        ""
        (let((cardinalNumber (cardinalNumber testSet))
            (lettersRemaining (calculateWordSize testSet index)))
          (createWord testSet (- index (numberOfWords cardinalNumber (- lettersRemaining 1))) cardinalNumber lettersRemaining))))))

(define testSet
  '(#\a #\b #\c))

(define f
  (fCreator testSet))

(f 30)

Aufgabe 6

Zeigen Sie, dass jede endliche Menge M aufzählbar ist.

Lösung:

Aufzählbar = abzählbar + berechenbar

Laut Definition heißt eine Menge M endlich, wenn es eine natürliche Zahl n gibt, sodass eine Bijektion zwischen M und der Menge aller natürlichen Zahlen kleiner als n existiert, d.h. jede endliche Menge ist abzählbar.

Eine Menge M heißt (rekursiv) aufzählbar wenn es entweder eine total berechenbare surjektive Funktion f:N \mapsto M gibt, oder es gilt M = \emptyset. Man nennt f eine Aufzählprozedur oder ein Aufzählverfahren von M.

Es gibt eine Funktion f, die als Eingabe die natürlichen Zahlen \N nimmt und auf jedes Element der endlichen Menge M abbildet. f ist berechenbar, da es eine total berechenbare surjektive Funktion f : \N \mapsto M gibt. Es wird der Reihe nach jedes Element aus \N einem Element aus M zugeordnet. Ist f surjektiv, können die restlichen Elemente aus \N auf ein beliebiges Element von M abgebildet werden. Somit ist f surjektiv, total und berechenbar.

Aufgabe 7

Die Menge G der Gitterpunkte (0,0),(0,1),... einer x-y-Ebene ist aufzählbar.

Geben Sie eine Funktion f an, die \N bijektiv auf G abbildet.
Definieren Sie eine Ordnungsrelation p< in G
Geben Sie eine Funktion k zur Berechnung der Platznummer k(x,y) des betrachteten Gitterpunktes (x,y) an.
Geben Sie eine Aufzählprozedur für G an und begründen Sie deren Berechenbarkeit.

Lösung:

zu 1.

g(z) = \begin{cases} (x,y) & \text{, mit } x=w-y,\\ & y = z - t \text{, wobei }\\\\ & w = \lfloor \frac{\sqrt{8z+1}-1}{2}\rfloor,\\\\ & t = \frac{w(w+1)}{2} \end{cases} \text{, mit }z\in\N

zu 2.

Die Paare sollen nach dem aufsteigendem Funktionswert der Funktion \pi (x,y) = \frac{(x + y)(x + y + 1)}{2} + y geordnet werden.

zu 3.

Die Funktion aus 2. sei k(x,y).

zu 4.

(define getX
    (lambda (z)
        (- (getW z) (getY z)) ))

(define getY
    (lambda (z)
        (- z (getT z))))

(define getW
    (lambda (z)
        (floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2))))

(define getT
    (lambda (z)
        (/ (* (getW z) (+ (getW z) 1)) 2)))

(define g
    (lambda (z)
        (cons (getX z) (getY z))))

(define pointStream (stream-map natstream g))

(define getStreamItems
    (lambda (stm cnt)
        (cond
            [(<= cnt 0) (cons '... '())]
            [else (cons (stream-car stm) (getStreamItems (stream-cdr stm) (- cnt 1)))])))

(getStreamItems pointStream 10)
;(stream-item pointStream 10)

Aufgabe 8

Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.

Aufgabe 9

Geben Sie für die Menge FIBS der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit. Weisen Sie nach, dass FIBS sogar entscheidbar ist.

Per Definition ist eine Menge M aufzählbar, wenn es eine totale berechenbare Prozedur f gibt, welche die Menge \N auf die Menge M abbildet. M ist hier die Menge der Fibonacci-Zahlwörter.

Überarbeiten!!! Die Aufzählprozedur lautet wie folgt:

f(n) = \begin{cases} g(n), & \text{wenn } g(n) \in \text{ M};\\ 0, & sonst. \end{cases}

Für g(n) gilt:

g(n) = \begin{cases} 0, & \text{wenn } n=0;\\ 1, & \text{wenn } n=1;\\ (n-1) + (n-2), & sonst. \end{cases}

Für beide, also für f und g, lassen sich entsprechende Scheme Ausdrücke angeben:

; g(n)
(define g
    (lambda (n) 
        (cond
            ((= n 0) 0)
            ((= n 1) 1)
            (else (+ (g (- n 1)) (g (- n 2)))))))

; natstream ist schon zu Begin dieser Wiki-Seite erstellt worden und kann einfach genutzt werden
(define fibstream stream-map natstream g)

(display "Die ersten 10 Elemente der Fibonacci-Menge\n")
(print-stream fibstream 10)

Es wird noch eine charakteristische Funktion \chi benötigt.

(define semi_chi
    (lambda (m w)
    (letrec
        (( helfer
           ( lambda ( stm )
              (if (string=? w (stream-car stm ))
                  #t
                  (helfer (stream-cdr stm ))))))
      (helfer m ))))

(semi_chi fibstream 5)

Aufgabe 10

Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen QZ = \{n^2 | n\in\N\}.

Aufgabe 11

Weisen Sie nach, dass die Menge M aller "Wörter" aus \{a,b\}^*, die mit a beginnen, semi-entscheidbar ist.

Aufgabe 12

Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki 30 Elemente der Vereinigungsmenge auszugeben.

M_1 ist die Menge der geraden Zahlen

f_1(i)=string(2i)

M_2 ist die Menge der ungeraden Zahlen

f_2(i)=string(2i+1)

Für die Vereinigung der beiden Mengen kann die folgende Funktion genommen werden:

h(i)=\begin{cases}f_1(\frac{i}{2}) & \text{, wenn }i\text{ gerade}\\f_2(\frac{i-1}{2}) & \text{, wenn }i\text{ ungerade}\end{cases}

; Die Funktion, die die Menge der geraden Zahlen berechnet
(define funktionGeradeZahlen
    (lambda (i)
       (* 2 i)))

; Die Funktion, die die Menge der ungeraden Zahlen berechnet
(define funktionUngeradeZahlen
    (lambda (i)
        (+ (* 2 i) 1)))

(define geraderStream (stream-map natstream funktionGeradeZahlen))
(define ungeraderStream (stream-map natstream funktionUngeradeZahlen))

; Funktion für die Vereinigungsmenge der beiden Streams
(define geradeVungerade-stream-maker
  (lambda (ungerade gerade)
    (letrec ((n 0)
             (geradeVungerade-stream-maker-helper
              (lambda (n ungeradestm geradestm)
                (if (even? n)
                    (stream-cons (stream-car geradestm) (geradeVungerade-stream-maker-helper (+ n 1) ungeradestm (stream-cdr geradestm)))
                    (stream-cons (stream-car ungeradestm) (geradeVungerade-stream-maker-helper (+ n 1) (stream-cdr ungeradestm) geradestm))))))
      (geradeVungerade-stream-maker-helper n ungerade gerade))))

(define mergeStream (geradeVungerade-stream-maker ungeraderStream geraderStream))

(display "gerade Zahlen\n")
(print-stream geraderStream 30)

(display "ungerade Zahlen\n")
(print-stream ungeraderStream 30)

(display "Vereinigungsmenge\n")
(print-stream mergeStream 30)