BuK/IIm11/BuK-Übung05

Wiki-Quelltext dieser Seite.

== Mathematik vs. Informatik ==
<language>Scheme</language>
=== Aufgabe 1 (Stefan Scheumann, Robert Rosenberger, Tobias Salzmann, Ronald Krause) ===
Defnieren Sie je eine totale Funktion für den Vorgänger und die Halbierung einer natürlichen Zahl. Defnieren Sie außerdem eine Funktion mit $ D_f = \N \setminus \{1234, 7266281\} $.


'''Lösung:'''


Funktionsdefinition Vorgänger (total) :  $ f(n) = n - 1$

Funktionsdefinition Vorgänger (partiell) : $$ f(n) = \begin{cases}
n - 1 ; & \text{für } n \in \N \setminus \{1234, 7266281\};\\
\bot; & sonst
\end{cases}
$$

Funktionsdefinition Halbiering (total) :  $ f(n) = n / 2$

Funktionsdefinition Vorgänger (partiell) : $$ f(n) = \begin{cases}
n / 2 ; & \text{für } n \in \N \setminus \{1234, 7266281\};\\
\bot; & sonst
\end{cases}
$$


<code id="4f9683759398b">(define vorgaenger
  (lambda (n)
    (- n 1)))

(define halbierung
  (lambda (n)
    (/ n 2)))

(define vorgaenger_partiell
  (lambda (n)
    (cond
      ((or (= n 1234) (= n 7266281)) (vorgaenger_partiell n))
      (else (vorgaenger n)))))

(define halbierung_partiell
  (lambda (n)
    (cond
      ((or (= n 1234) (= n 7266281)) (halbierung_partiell n))
      (else (halbierung n)))))</code>
<run id="4f968375939f3">(halbierung_partiell 1234)</run>

<language>Scheme</language>
== Postsches Korrrespondenzprobelm PCP (Jens Heider, Daniel Tasche) ==
=== Aufgabe 1 ===
Für K = ((001; 0)(01; 011); (01; 101); (10; 001)) gibt es eine Lösung. Die gesuchte Indexfolge heißt

(2 4 3 4 4 2 1 2 4 3 4 3 4 4 3 4 4 2 1 4 4 2 1 3 4 1 1 3 4 4 4 2 1 2 1 1 1 3 4 3 4 1 2 1 4 4 2 1 4 1 1 3 4 1 1 3 1 1 3 1 2 1 4 1 1 3)

Uberprüfen Sie die angegebene Lösung per Hand.

Lösung siehe Bild...

[[Bild:Sijeheid_2012-04-22-025.jpg]]


=== Aufgabe 2 ===
Entwickeln Sie eine Scheme-Prozedur (ProgrammingWiki), die bei Aufruf für eine gegebene Instanz eine Lösung des PCP findet, falls eine solche existiert und der Rechenaufwand im Rahmen bleibt.

<code id="4f95745864a22">
(define erstelle-zeile
  (lambda (ill len)
    (letrec (
         (helper
           (lambda (liste len)
             (if (> len 0)
                 (append (helper liste (- len 1)) (list (append liste (list len))))
                 '()
                 )
             )
           ))    
      (if (null? ill)
        '()
        (append (list (car ill)) (helper (car ill) len) (erstelle-zeile (cdr ill) len))
      )
    )
  )
)

(define erstelle-ill
  (lambda (len depth)
    (letrec (
      (erstelle-initialliste (lambda (len)
                (if (> len 0)
                    (append (erstelle-initialliste (- len 1)) (list (list len)))
                    '()
                )
              )
      )
      (helper (lambda (depth ill)
                (if (> depth 0)
                    (erstelle-zeile (helper (- depth 1) ill) len)
                    (erstelle-zeile (erstelle-initialliste len) len)
                )
              )
      ))
      (helper depth '())
    )
  )
)

(define get-item 
  (lambda (liste index)
    (letrec
        ((helper (lambda (rl current-index)
                   (cond
                     ((= current-index index) (car rl))
                     ((null? rl) null)
                     (else (helper (cdr rl) (+ current-index 1)))
                   )
                 )
        ))
      (helper liste 1)
    )
  )
)

(define pcp
  (lambda (pairs depth)
    (letrec
        ((erzeuge-wort (lambda (fn il)
                  (if (null? il)
                      ""
                      (string-append (fn (get-item pairs (car il))) (erzeuge-wort fn (cdr il)))
                  )
         ))
         (helper (lambda (reduced-ill)
                   (if (null? reduced-ill)
                       #f
                       (if (string=? (erzeuge-wort car (car reduced-ill)) (erzeuge-wort cadr (car reduced-ill)))
                           (car reduced-ill)
                           (helper (cdr reduced-ill))
                       )
                   )
        )))
      (helper (erstelle-ill (length pairs) depth))
      )
  )
)
</code>

<run id="4f95745864a91">
(pcp '(("1" "101") ("10" "00") ("011" "11")) 2)
</run>

== Turing-Maschine und Churchsche These ==
=== Turing-Maschine als Akzeptator (Stefan Lüttke, Felix Nitsche) ===
Geben Sie Trichterbilder für den Einsatz einer TM als Akzeptator an:
* für semi-entscheidbare Sprachen
[[Bild:Sistluet_Trichter_semi_entscheid.png|250px]]

* für entscheidbare Sprachen
[[Bild:Sistluet_Trichter_entscheid.png|250px]]

=== Turing-Aufzählbarkeit, Turing-Entscheidbarkeit (Max Wielsch, Raik Bieniek, Ingo Körner, Christof Ochmann) ===
Definieren Sie die Begriffe Turing-aufzählbar und Turing-entscheidbar analog zur Turing-Berechenbarkeit.

Sei A ein Alphabet, $M \subseteq A^*$. M heißt Turing-entscheidbar, falls die charakteristische Funktion $\chi_M$  Turing-berechenbar ist.

M heißt Turing-aufzählbar, wenn es eine Funktion $f: N \rightarrow M$ gibt, die surjektiv und Turing-berechenbar ist.