BuK/IIm11/BuK-Übung06

Wiki-Quelltext dieser Seite.

[http://www.inf.hs-zigr.de/~wagenkn/TI/Berechenbarkeitstheorie/VL/vl06.pdf Vorlesungsfolien]

Aufgaben werden am 08.05. um 23:00 übertragen


== Reduzierbarkeit ==

<language>Scheme</language>
=== Aufgabe 1 (Max Wielsch, Raik Bienik) ===
(Aufgabe siehe: VL Slide 14)

Konstruieren sie eine Prozedur, welche prüft ob $w$ die Form $uu$ besitzt!

<code id="4fa96b851b96b">
(define sublist
  (lambda (list start)
    (if (= start 0)
      list
      (sublist (cdr list) (- start 1)))))

(define size
  (lambda (list)
    (if (null? list)
      0
      (+ (size (cdr list)) 1))))

;checks if wordAsList has letterCount letter(s) at position start.
(define checkLetters
  (lambda (wordAsList start letter letterCount)
    (letrec ((worker (lambda (list letterCount)
        (if (= letterCount 0)
          '#t
          (if (equal? (car list) letter)
            (worker (cdr list) (- letterCount 1))
            '#f)))))
      (worker (sublist wordAsList start) letterCount))))

(define acceptor
  (lambda (w)
    (let* ((wAsList (string->list w))
	  (sizeofW (size wAsList)))
      (if (not (= (modulo sizeofW 6) 0))
        '#f
        (let ((letterCount (quotient sizeofW 6)))
          (if
            (and
              (checkLetters wAsList (* 0 letterCount) #\a letterCount)
              (checkLetters wAsList (* 1 letterCount) #\b letterCount)
              (checkLetters wAsList (* 2 letterCount) #\c letterCount)
              (checkLetters wAsList (* 3 letterCount) #\a letterCount)
              (checkLetters wAsList (* 4 letterCount) #\b letterCount)
              (checkLetters wAsList (* 5 letterCount) #\c letterCount))
            '#t
            '#f))))))
</code>
<run id="4fa96b851b9d3">
(acceptor "aaabbbcccaaabbbccc")
</run>

=== Aufgabe 2 (Stefan Lüttke, Felix Nitsche) ===
(Aufgabe siehe: VL Slide 15/16)

Beweisen Sie diesen Satz, indem Sie mittels Aussagenlogik die Äquivalenz dieser Aussage zum vorhergehenden Satz zeigen. Es handelt sich um die Kontraposition:

$A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A$

Verwenden Sie im Beweis die folgenden Aussagen:

A: $P'$ ist entscheidbar. B: $P$ ist reduzierbar auf $P'$. C: $P$ ist
entscheidbar.

-----

Der Beweis kann in Form einer Wahrheitstabelle erbracht werden. Dabei werden die folgenden Variabeln genutzt:

$A: P'$  ist entscheidbar

$B: P$  ist reduzierbar auf $P'$

$C: P$  ist entscheidbar


Als gegeben kann dabei nach Satz 1 betrachtet werden dass:

$A \wedge B \Rightarrow C$

zu beweisen ist:

$\neg C \wedge B \Rightarrow \neg A$


Beweis:

{| border="1" cellpadding="5" cellspacing="0"
!$Zeile$
!$A$
!$B$
!$C$
!$E=A \wedge B$
!$F=E\Rightarrow C$
!$G=\neg C \wedge B$
!$H = G \Rightarrow \neg A$
!$I = F \Leftrightarrow H$
!$Kommentar$
|-
|| 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 ||style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | gegeben durch Satz 1
|-
|| 2 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | falsch nach Satz 1
|-
|| 3 ||1 || 0 || 1 || 0 || 1 || 0 || 1 || 1 || ...
|-
|| 4 ||1 || 0 || 0 || 0 || 1 || 0 || 1 || 1 || ...
|-
|| 5 ||0 || 1 || 1 || 0 || 1 || 0 || 1 || 1 || ...
|-
|| 6 || style="background-color:#9FF781" | 0 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 0 || style="background-color:#9FF781" | 0 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | Einzig verbleibende Möglichkeit für $\neg C \wedge B$
|-
|| 7 ||0 || 0 || 1 || 0 || 1 || 0 || 1 || 1 || ...
|-
|| 8 ||0 || 0 || 0 || 0 || 1 || 0 || 1 || 1 || ...

|-

|}


In Zeile 6 befindet sich die einzig verbleibende Möglichkeit für $\neg C \wedge B$. Daraus kann abgelesen werden dass in dem Fall $\neg A$ gilt, womit Satz 2 bewiesen ist.

== Unentscheidbarkeitsbeweis ==
=== Aufgabe 1 (Ingo Körner, Christoph Ochmann) ===
(Aufgabe siehe: VL Slide 13)

Zeigen Sie die Unentscheidbarkeit (Semi-Entscheidbarkeit) von $L_{\Sigma^{*}}:=\{\left\langle M \right\rangle | L(M) = \Sigma^{*} \}$ durch Reduktion der Sprache $L_{\Sigma^{*}}$ auf das Halteproblem.

Schreibe für alle Eingabewörter aus $\Sigma^{*}$ die Kodierung der Maschine M, d.h. <M>, sowie w $\in$ $\Sigma^{*}$ auf das Band einer Maschine $M_2$. Die Maschine $M_2$ ist so konstruiert, dass sie aus ihrer Eingabe <M> und w die Kodierung einer Maschine M', d.h. <M'>, zusammen mit einem Eingabewort y auf ihr Band als Ausgabe schreibt. Die Besonderheit von M' ist, dass diese Maschine mit dem Eingabewort y stoppt, wenn M(w) stoppen würde. Dabei ist y nur ein Platzhalter, denn y hat auf die Terminierung von M' keinen Einfluss. Als nächstes wird <M'> und y auf das Band einer UTM $M_1$ geschrieben. $M_1$ führt die Kodierung der Maschine M' mit dem Wort y aus. Dabei verwirft die Maschine M' als erstes ihr Eingabewort y, so dass ihr Band leer ist. Wenn die durch $M_1$ ausgeführte Maschine M' mit ihrem leeren Band hält, so heißt das, dass auch die Maschine M mit dem Wort w akzeptieren würde. Wenn die durch die Maschine $M_1$ ausgeführte Maschine M' auf dem anfangs leeren Band nicht in einem Endzustand hält, dann stoppt auch die Maschine M mit dem Wort w nicht in einem Endzustand. <M> ist $\in$ $L_{\Sigma^{*}}$ genau dann, wenn M' termiert.