Übungsaufgaben Theoretische Informatik und Logik

Diese Notizen sind während meiner Vorbereitung für die Prüfung Theoretische Informatik und Logik entstanden.

• Link zur Vorlesung
• Link zu den Online-Vorlesungen (Sommersemester 2021)

Wenn Lösungen mit TODO markiert sind, sind diese nicht richtig ausgearbeitet und sollten eigentlich später nochmal genauer betrachtet werden.

Disclaimer: Das ganze hat für die Note 3,0 gereicht.

1. Übungsblatt

Aufgabe B

Zeigen Sie: Wenn es möglich ist, für zwei beliebige Turing-Maschinen zu entscheiden, ob sie dieselbe Sprache akzeptieren, so ist es auch möglich, für beliebige Turing-Maschinen zu entscheiden, ob sie die leere Sprache akzeptieren.

gesucht: Erkennt die Turing-Maschine $M$ die leere Sprache $L(M) = \emptyset$?

• Konstruktion einer Turing-Maschine $M_\emptyset$, die für jedes Wort $w$ ablehnt $\Rightarrow L(M_\emptyset) = \emptyset$
• Entscheide, ob $M$ und $M_\emptyset$ die gleiche Sprache erkennen:
  • $M$ und $M_\emptyset$ erkennen die gleiche Sprache $\Rightarrow L(M) = \emptyset$
  • $M$ und $M_\emptyset$ erkennen nicht die gleiche Sprache $\Rightarrow L(M) \neq \emptyset$

Aufgabe 1.1

Zeigen Sie folgende Aussagen:
c) $\left|\mathbb{R}\right| \neq \left|\mathbb{N}\right|$

siehe Cantors zweites Diagonalargument

Zeigen Sie folgende Aussagen:
d) für jede nicht-leere endliche Menge $\Sigma$ ist $\Sigma^{*}$ abzählbar unendlich.

besser $f : \mathbb{N} \rightarrow \Sigma^{*}$:

• $\Sigma = \left\{ a_1, a_2, \ldots, a_n \right\}$, $w \in \Sigma^{*}$
• $\left| w \right| = 0$
  • $1 \mapsto w = \varepsilon$
  ($\left| \ldots \right| = n^0 = 1$)
• $\left| w \right| = 1$ (falls $\left| a_1 \right| = \left| a_2 \right| = \ldots = \left| a_n \right| = 1$)
  • $2 \mapsto w = a_1$
  • $3 \mapsto w = a_2$
  • $\ldots$
  • $n + 1 \mapsto w = a_n$
  ($\left| \ldots \right| = n$)
• $\left| w \right| = 2$ (falls $\left| a_1 \right| = \left| a_2 \right| = \ldots = \left| a_n \right| = 1$)
  • $n + 2 \mapsto w = a_1 a_1$
  • $n + 3 \mapsto w = a_2 a_1$
  • $\ldots$
  • $2n + 1 \mapsto w = a_n a_1$
  • $2n + 2 \mapsto w = a_1 a_2$
  • $2n + 3 \mapsto w = a_1 a_2$
  • $\ldots$
  • $3n + 1 \mapsto w = a_n a_2$
  • $3n + 2 \mapsto w = a_1 a_3$
  • $\ldots$
  • $(n + 1) n + 1 \mapsto w = a_n a_n$
  ($\left| \ldots \right| = n^2$)
• $\ldots$

wahrscheinlich falsch:

1. $\Sigma^{*} = \{\varepsilon\} \cup \Sigma \cup \Sigma^2 \cup \ldots$
2. $\left|\Sigma\right| = \left|\mathbb{N}\right|$
3. $\left|\Sigma^{*}\right| = 1 + \left|\mathbb{N}\right| + \left|\mathbb{N} \times \mathbb{N}\right| + \left|\mathbb{N} \times \mathbb{N} \times \ldots\right| + \ldots$
4. $\left|\mathbb{N} \times \mathbb{N}\right| = \left|\mathbb{N}\right|$
   $\Rightarrow \left|\mathbb{N} \times \mathbb{N} \times \mathbb{N}\right| = \left|\mathbb{N}\right|$
   $\Rightarrow \ldots$
5. $\left|\mathbb{N}\right| + \left|\mathbb{N}\right| = \left|\mathbb{N}\right|$
6. $\left|\Sigma^{*}\right| = \left|\mathbb{N}\right|$

Aufgabe 1.2

Geben Sie für folgende Sprachen Aufzähler an:
a) $L_1 = \{3n | n \in \mathbb{N}\}$, wobei die Ausgabe unär kodiert sein soll

turingmachine.io

input: "11"
blank: _
start state: mark_input_end
table:
  mark_input_end:
    1: {R: mark_input_end}
    _: {write: S, L: move_left}
  move_left:
    [1, S]: L
    _: {R: take1}
  take1:
    1: {write: _, R: append3}
    S: {write: _, R: done}
  append3:
    [1, S]: R
    _: {write: 1, R: append2}
  append2:
    _: {write: 1, R: append1}
  append1:
    _: {write: 1, L: move_left}
  done:

(siehe auch 1.4 b)

Geben Sie für folgende Sprachen Aufzähler an:
b) $L_2 = \{a^n b^n | n \in \mathbb{N}\}$

turingmachine.io

input: "111"
blank: _
start state: move_right
table:
  move_right:
    1: R
    [_, a]: {L: prepend_a}
  prepend_a:
    [a, b]: L
    _: {R: done}
    1: {write: a, R: append_b}
  append_b:
    [a, b]: R
    _: {write: b, L: prepend_a}
  done:

Aufgabe 1.3

a) Konstruieren Sie eine Turing-Maschine $A_{mul}$, welche die Multiplikation zweier natürlicher Zahlen implementiert. Dabei sollen sowohl die Eingaben als auch die Ausgabe unär kodiert sein.

turingmachine.io

input: "11_111"
blank: _
start state: skip_right_a
table:
  skip_right_a:
    1: R
    _: {R: skip_right_b}
  skip_right_b:
    1: R
    _: {write: S, L: skip_left_b}
  # move left over the inputs
  skip_left_b:
    1: L
    _: {L: skip_left_a}
  skip_left_a:
    1: L
    _: {R: take1}
  # subtract one from a
  take1:
    1: {write: _, R: skip_input}
    _: {R: cleanup}
  # skip right over inputs and outputs
  skip_input:
    [_, 1]: R
    S: {R: skip_output}
  skip_output:
    1: R
    _: {L: skip_output_to_b}
  # add 1 to output for every 1 in b and turn 1 to 2 in b
  skip_output_to_b:
    1: L
    S: {L: flip_b}
  flip_b:
    2: L
    1: {write: 2, R: append_1}
    _: {R: unflip_b}
  append_1:
    [2, S, 1]: {R: append_1}
    _: {write: 1, L: skip_output_to_b}
  # turn 2 to 1 in b
  unflip_b:
    2: {write: 1, R: unflip_b}
    S: {L: skip_left_b}
  # erase up to and including "S"
  cleanup:
    [_, 1]: {write: _, R: cleanup}
    S: {write: _, R: done}
  done:

Aufgabe 1.4

Auf Folie 27 der 2. Vorlesung vom 11.4.2024 wird innerhalb des Widerspruchsbeweises zur Berechenbarkeit der Busy-Beaver-Funktion eine Turingmaschine $M_{*2}$ mit Alphabet $\{x, ␣\}$ verwendet, welche die Funktion $x^n \rightarrow x^{2n}$ berechnet.
b) Geben Sie eine Einband-Turingmaschine über dem Alphabet $\{x, ␣\}$ an, die die Funktion $x^n \rightarrow x^{2n}$ berechnet.

turingmachine.io

input: "xxxx"
blank: _
start state: add_space
table:
  add_space:
    x: {write: _, L: prepend_x}
    _: {R: skip_x0_right_x}
  prepend_x:
    _: {write: x, L: add_space}
  skip_x0_right_x:
    x: {R: skip_x0_right_0}
    _: {L: fill_space_left_0}
  skip_x0_right_0:
    _: {R: skip_x0_right_x}
    x: {L: add_space}
  fill_space_left_0:
    _: {write: x, L: fill_space_left_x}
  fill_space_left_x:
    x: {L: fill_space_left_0}
    _: {R: cleanup}
  cleanup:
    x: {write: _, R: done}
  done:

2. Übungsblatt

Aufgabe C

Zeigen Sie, dass $\{1\}^{*}$ unentscheidbare Teilmengen besitzt.

Die Potenzmenge einer abzählbar unendlichen Menge ist überabzählbar.

Cantors Diagonalargument:

• $\mathcal{P}(A) = \left\{ S_1, S_2, S_3, \ldots \right\}$
• $T = \left\{ a_i | a_i \in A, a \notin S_i \right\}$
• $\Rightarrow T$ enthält $a_i$, aber $S_i$ nicht $\Rightarrow T \neq S_i$
  • $\Rightarrow T$ enthält $a_1$, aber $S_1$ nicht $\Rightarrow T \neq S_1$
  • $\Rightarrow T$ enthält $a_2$, aber $S_2$ nicht $\Rightarrow T \neq S_2$
  • $\ldots$
• $\Rightarrow T \notin \mathcal{P}(A)$
• $\Rightarrow \mathcal{P}(A)$ ist überabzählbar.

Aufgabe D

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
d) Die Ackermannfunktion ist total und damit LOOP-berechenbar.

siehe 3. Vorlesung, Seite 17ff

Aufgabe 2.1

Zeigen Sie, dass folgende Funktionen $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ LOOP-berechenbar sind:
a) $f(x, y) := \text{max}(x - y, 0)$

While simulator

result := x + 0
LOOP y DO
  result := result - 1
END

Zeigen Sie, dass folgende Funktionen $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ LOOP-berechenbar sind:
b) $f(x, y) := x \cdot y$

result := 0
LOOP x DO
  LOOP y DO
    result := result + 1
  END
END

Zeigen Sie, dass folgende Funktionen $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ LOOP-berechenbar sind:
c) $f(x, y) := \text{max}(x, y)$

While simulator

result := x
LOOP x DO
  y := y - 1
END
LOOP y DO
  result := result + 1
END

Zeigen Sie, dass folgende Funktionen $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ LOOP-berechenbar sind:
d) $f(x, y) := \text{ggT}(x, y)$

While simulator, Euklidischer Algorithmus

(Beim Verwenden von IF x != 0 THEN scheint es einen Bug zu geben und das ganze Programm einfach nicht zu laufen.)

result := b
# <if a > 0>
nonzero := 0
LOOP a DO
  nonzero := 1
END
LOOP nonzero DO
# </if a > 0>
  LOOP b DO
    # <if b > 0>
    nonzero := 0
    LOOP b DO
      nonzero := 1
    END
    LOOP nonzero DO
    # </if b > 0>
      # now we are inside WHILE b != 0
      aminusb := a
      LOOP b DO
        aminusb := aminusb - 1
      END
      # <if aminusb > 0>
      nonzero := 0
      LOOP aminusb DO
        nonzero := 1
      END
      else := 1
      LOOP nonzero DO
      # </if aminusb > 0>
        # if a > b
        LOOP b DO
          a := a - 1
        END
        else := 0
      END
      LOOP else DO
        # if b <= a
        LOOP a DO
          b := b - 1
        END
      END
    END
  END
  result := a
END

Aufgabe 2.3

Zeigen Sie, dass es keine Many-One-Reduktion vom Halteproblem $P_\text{halt}$ von Turing-Maschinen auf das Leerheitsproblem
$P_\text{leer} := \{\text{enc}(M) | L(M) = \emptyset\}$
von Turing-Maschinen gibt.

• $P_\text{halt}$ ist semi-entscheidbar und unentscheidbar. Daraus folgt $P_\text{halt}$ ist nicht co-semi-entscheidbar. (Wäre $P_\text{halt}$ semi-entscheidbar und $\neg P_\text{halt}$ ebenfalls semi-entscheidbar (gleichbedeutend mit $P_\text{halt}$ ist co-semi-entscheidbar), wäre $P_\text{halt}$ entscheidbar.)

• $P_\text{halt}$ ist nicht co-semi-entscheidbar und $P_\text{halt} \leq_m P_\text{leer}$
  $\Rightarrow$ $P_\text{leer}$ ist nicht co-semi-entscheidbar
  $\Leftrightarrow$ $\neg P_\text{leer} := \{\text{enc}(M) | L(M) \neq \emptyset\}$ (das Komplement zu $P_\text{leer}$) ist nicht semi-entscheidbar

• Um einen Widerspruch herbeizuführen, ist zu zeigen, dass $\neg P_\text{leer}$ semi-entscheidbar ist, bspw. mit einer Reduktion $\neg P_\text{leer} \leq_m P_\text{halt}$.

  Wikipedia verweist auf Introduction to Automata Theory, Languages, and Computation (3rd Edition). In Kapitel 9.3.2 Turing Machines That Accept the Empty Language (Seite 410) wird $P_\text{leer}$ als $L_e$ eingeführt und $L_{ne} = \neg P_\text{leer} = \{\text{enc}(M) | L(M) \neq \emptyset\}$.

  Theorem 9.8 beweist, dass $\neg P_\text{leer}$ semi-entscheidbar ist ($L_u$ ist in Kapitel 9.2.3 (Seite 403) als die Sprache der Universellen Turing-Maschine definiert ($L_u = \{\text{enc}(M, w) | M$ ist eine Turing-Maschine, $w \in L(M)\}$).):

  • Konstruktion einer nicht-deterministische Turing-Maschine $M_\text{Orakel}$ mit der Eingabe $\text{enc}(M) \in \neg P_\text{leer}$
  • $M_\text{Orakel}$ nutzt seine nicht-deterministischen Fähigkeiten, um $w \in L(M)$ zu raten.
  • $w$ wird auf das Band geschrieben.
  • Halteproblem:
    • Die Turing-Maschine $M$ wird auf $w$ simuliert.
    • Akzeptiert $M$, so akzeptiert auch $M_\text{Orakel}$.

  Sollte $M$ also irgendeine Eingabe akzeptieren ($L(M) \neq \emptyset$), rät $M_\text{Orakel}$ diese und akzeptiert somit die Eingabe $\text{enc}(M)$.

  Damit ist $\neg P_\text{leer}$ semi-entscheidbar.

  Widerspruch: Es kann somit keine Many-One-Reduktion $P_\text{halt} \leq_m P_\text{leer}$ geben.

siehe auch:

• “Berechenbarkeit #33 - Epsilon-Halteproblem und Leerheitsproblem sind unentscheidbar” von @NLogSpace (ab 8min)
• “Berechenbarkeit #36 - Semi-Entscheidbarkeit” von @NLogSpace

Aufgabe 2.4

Zeigen Sie, dass jede semi-entscheidbare Sprache $L$ auf das Halteproblem $P_\text{halt}$ many-one-reduziert werden kann.

Dazu muss eine totale turing-berechenbare Funktion $f : L \rightarrow P_\text{halt}$ gefunden werden. Da $L$ semi-entscheidbar ist existiert eine Turing-Maschine $M_L$, die alle Worte $w \in L$ akzeptiert und ewig läuft, wenn $w \notin L$.

Idee: $f(w)$ mit $w \in L$ konstruiert einer Turing-Maschine $M_w$, die zuerst das Band löscht, dann $w \in L$ auf das Band schreibt und anschließend das Halteproblem $\text{enc}(M_L, w) \in P_\text{halt}$ simultiert.

Wenn $M_L$ auf $w$ hält, hält auch $M_w$ und die Eingabe $w \in L$ wird akzeptiert. Ist $w \notin L$ läuft $M_L$ und damit auch $M_w$ ewig.

3. Übungsblatt

Aufgabe E

Geben Sie eine Turing-Maschine $A_{\mod 2}$ an, die die Funktion $f : N \rightarrow N$ mit $f(x) = (x \mod 2)$ berechnet. Stellen Sie dabei die Zahlen in unärer Kodierung dar.

turingmachine.io

input: "11111"
blank: _
start state: even
table:
  even:
    1: {write: _, R: odd}
    _: {R: undo_move_right}
  odd:
    1: {write: _, R: even}
    _: {write: 1, R: undo_move_right}
  undo_move_right:
    _: {L: done}
  done:

Aufgabe G

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
a) Die Menge der Instanzen des Postschen Korrespondenzproblems, welche eine Lösung haben, ist semi-entscheidbar.

wahr, das PCP ist semi-enscheidbar. Wenn ein PCP mit $n$ “Dominosteinen” eine Lösung der Länge $m$ hat, dann kann diese Lösung mittels Brute-Force in $O(n^m)$ gefunden werden und die Turing-Maschine hält.

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
b) Das Postsche Korrespondenzproblem ist bereits über dem Alphabet $\Sigma = \left\{ a, b \right\}$ nicht entscheidbar.

wahr, TODO

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
c) Es ist entscheidbar, ob eine Turingmaschine nur Wörter akzeptiert, die Palindrome sind. (Ein Palindrom ist ein Wort $w = (a_1, \ldots, a_n)$ mit $(a_1, \ldots, a_n) = (a_n, \ldots, a_1)$.)

falsch, TODO $P_\text{halt} \leq_m P_\text{Palindrom}$

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
d) $P_\text{halt}$ ist semi-entscheidbar.

wahr

$P_\text{halt} := \left\{ \text{enc}(M, w) | \text{$M$ hält auf $w$} \right\}$

Konstruktion einer Turing-Maschine $M_\text{halt}$ mit der Eingabe $\text{enc}(M, w)$ als Semi-Entscheider für $P_\text{halt}$:

• lösche das Band $w$
• schreibe $w$ auf das Band
• simuliere $M$ auf $w$
• akzeptiert $M$, dann war $\text{enc}(M, w) \in P_\text{halt}$
• hält $M$ nicht, hält auch $M_\text{halt}$ nicht
• $\Rightarrow$ semi-entscheidbar

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
e) Es ist nicht entscheidbar, ob die von einer deterministischen Turing-Maschine berechnete Funktion total ist.

wahr: Ist $f$ total? $\Leftrightarrow$ Hält $M_f$ für $w$? $\Leftrightarrow \text{enc}(M_f, w) \in P_\text{halt}$

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
f) Es gibt reguläre Sprachen, die nicht semi-entscheidbar sind.

Aufgabe 3.1

Besitzen folgende Instanzen $P_i$ des Postschen Korrespondenzproblems Lösungen? Begründen Sie Ihre Antwort.

a) $P1$
$a$	$abaa$	$ab$
$aaa$	$ab$	$b$

Lösung für $s_a = (1, 0), \left| s_a \right| = 2$

Besitzen folgende Instanzen $P_i$ des Postschen Korrespondenzproblems Lösungen? Begründen Sie Ihre Antwort.

b) $P2$
$ab$	$baa$	$aba$
$aba$	$aa$	$baa$

womöglich, aber keine Lösung für $\left| s_b \right| < 16$

Besitzen folgende Instanzen $P_i$ des Postschen Korrespondenzproblems Lösungen? Begründen Sie Ihre Antwort.

c) $P3$
$bba$	$ba$	$ba$	$ab$
$b$	$baa$	$aba$	$bba$

womöglich, aber keine Lösung für $\left| s_c \right| < 12$

import multiprocessing
from functools import cache

post = [
    # ("a", "aaa"),
    # ("abaa", "ab"),
    # ("ab", "b"),
    ("ab", "aba"),
    ("baa", "aa"),
    ("aba", "baa"),
    # ("bba", "a"),
    # ("ba", "baa"),
    # ("ba", "aba"),
    # ("ab", "bba"),
]


@cache
def path_to_strings(path):
    if not path:
        return ([], [])
    a, b = path_to_strings(path[:-1])
    i = path[-1]
    return (a + [post[i][0]], b + [post[i][1]])


def find_solution(worker_num, q, finished):
    depth = 0
    while True:
        path = q.get()
        if len(path) > depth:
            depth = len(path)
            print("worker", worker_num, "depth:", depth)
        assert depth < 20
        # generate both strings
        top, bottom = path_to_strings(path)
        if "".join(top) == "".join(bottom):
            finished.put(path)
            break
        # create new paths from the curent path plus each tuple
        for i in range(len(post)):
            q.put(path + (i,))


# intial paths of length 1 each starting with another PCP tuple
q = multiprocessing.Queue()
for i in range(len(post)):
    q.put((i,))

# start 8 processes that will write their results to finished
finished = multiprocessing.Queue()
workers = [
    multiprocessing.Process(target=find_solution, args=(i, q, finished))
    for i in range(8)
]
for worker in workers:
    worker.start()
try:
    # wait for the first result
    result = finished.get()
finally:
    # kill all workers
    for worker in workers:
        worker.kill()
        worker.join()
# print result
print(result)
top, bottom = path_to_strings(result)
print(top, "==", bottom)

Aufgabe 3.2

Zeigen Sie, dass das Postsche Korrespondenzproblem über einem einelementigen Alphabet entscheidbar ist.

Jede Instanz des Postschen Korrespondenzproblem über einem einelementigen Alphabet $\Sigma = \{a\}$ ist durch eine Menge $\{p_{(i_1,j_1)}, p_{(i_2,j_2)}, \ldots, p_{(i_n,j_n)}\}$, wobei $p_{(i,j)} = (a^i, a^j)$, gegeben. Die Lösung ist berechenbar, genau dann wenn eine Lösung $s = (s_1, s_2, \ldots, s_n)$ existiert:

• $(a^{i_1})^{s_1} \cdot (a^{i_2})^{s_2} \cdot \ldots \cdot (a^{i_n})^{s_n} = (a^{j_1})^{s_1} \cdot (a^{j_2})^{s_2} \cdot \ldots \cdot (a^{j_n})^{s_n}$
  (Die Reihenfolge der Elemente in der Lösung $p_{i_k,j_k}$ ist beliebig vertauschbar, da $\Sigma = \{a\}$.)
• Die erzeugten Worte sind gleich, wenn sie die gleiche Länge haben.
  $\Rightarrow i_1 s_1 + i_2 s_2 + \ldots + i_n s_n = j_1 s_1 + j_2 s_2 + \ldots + j_n s_n$
• $\Rightarrow (i_1 - j_1) s_1 + (i_2 - j_2) s_2 + \ldots + (i_n - j_n) s_n = 0$
• Lösbarkeit:
  • $i_{k} = j_{k}$ (triviale Lösung):
    • $s_k = 1$
    • $s_{k' | k' \neq k} = 0$
  • $i_{k_1} > j_{k_1}$ und $i_{k_2} < j_{k_2}$:
    • $s_{k_1} = j_{k_2} - i_{k_2}$
    • $s_{k_2} = i_{k_1} - j_{k_1}$
    • $s_{k' | k' \neq k_1, k' \neq k_2} = 0$
    $\Rightarrow \bm{+} (i_{k_1} - j_{k_1}) \bm{(j_{k_2} - i_{k_2})} + (i_{k_2} - j_{k_2}) (i_{k_1} - j_{k_1}) = 0$
    $\Leftrightarrow \bm{-} (i_{k_1} - j_{k_1}) \bm{(i_{k_2} - j_{k_2})} + (i_{k_2} - j_{k_2}) (i_{k_1} - j_{k_1}) = 0$
  • sonst alle $i_k > j_k$ oder alle $i_k < j_k$: $\nexists s_k > 0$

Es ist also lediglich zu prüfen, ob die Instanz

• ein Element $p_{(i_k,i_k)}$ beinhaltet oder
• zwei Elemente
  • $p_{(i_{k_1}, j_{k_1})}$ mit $i_{k_1} > j_{k_1}$ und
  • $p_{(i_{k_2},j_{k_2})}$ mit $i_{k_2} < j_{k_2}$
  beinhaltet.

Beispiele:

1. $P_1 = \{p_{(5,2)}, p_{(1,3)}\}$
   $\Rightarrow 5 s_1 + 1 s_2 = 2 s_1 + 3 s2$
   $\Rightarrow 3 s_1 - 2 s_2 = 0$
   $\Rightarrow s_1 = 2, s_2 = 3$

2. $P_2 = \{p_{(1,2)}, p_{(2,3)}\}$
   $\Rightarrow 1 s_1 + 2 s_2 = 2 s_1 + 3 s2$
   $\Rightarrow 1 s_1 + 1 s_2 = 0$
   $\Rightarrow \nexists s_1 > 0, s_2 > 0$

Aufgabe 3.3

Es sei $T := \{\text{enc}(M) | M$ ist eine Turing-Maschine, welche $w^R$ akzeptiert, falls sie $w$ akzeptiert$\}$, wobei $w^R$ das zu $w$ umgekehrte Wort ist. Zeigen Sie, dass $T$ nicht entscheidbar ist.

Beweis: $P_\text{halt} \leq_m T$

Redunktionsfunktion $f : P_\text{halt} \rightarrow T$

• $f(\text{enc}(M, w))$ für $\text{enc}(M, w) \in P_\text{halt}$ konstruiert eine Turing-Maschine $M_T$
• $M_T$ simuliert $M$ auf $w$
• Da $w \in L(M)$, akzeptiert $M$ $w$.
• $M_T$ wird erweitert, dass $M_T$ auch $w_R$ akzeptiert.
• $\Rightarrow L(M_T) = \{w, w^R\}$
  $\Rightarrow \text{enc}(M_T) \in T$

Da $P_\text{halt}$ nicht entscheidbar ist und $P_\text{halt} \leq_m T$ existiert, ist $T$ nicht entscheidbar.

Aufgabe 3.4

Zeigen Sie, dass weder das Äquivalenzproblem $P_\text{äquiv}$ für Turing-Maschinen noch dessen Komplement $\neg P_\text{äquiv}$ semi-entscheidbar ist, wobei

• $P_\text{äquiv} := \{\text{enc}(M_1)\#\#\text{enc}(M_2) | L(M_1) = L(M_2)\}$,
• $\neg P_\text{äquiv} := \{\text{enc}(M_1)\#\#\text{enc}(M_2) | L(M_1) \neq L(M_2)\}$.

Zeigen Sie dazu, dass $P_\text{halt} \leq_m P_\text{äquiv}$ und $P_\text{halt} \leq_m \neg P_\text{äquiv}$ gilt. Weshalb zeigt dies die Aussage?

$P_\text{halt} \leq_m P_\text{äquiv}$

• $f(\text{enc}(M, w)) := \text{enc}(M)\#\#\text{enc}(M)$ für $\text{enc}(M, w) \in P_\text{halt}$
• $\text{enc}(M)\#\#\text{enc}(M) \in P_\text{äquiv}$, da $L(M) = L(M)$

$P_\text{halt} \leq_m \neg P_\text{äquiv}$

• $f(\text{enc}(M, w)) := \text{enc}(M)\#\#\text{enc}(M')$ für $\text{enc}(M, w) \in P_\text{halt}$
• $M'$ ist eine Turing-Maschine, die ein $w' \notin L(M)$ akzeptiert, z.B.:
  • $\Sigma_{M'} := \Sigma_M \cup \{\land\}$ mit $\land \notin \Sigma_M$
  • $M'$ erwartet als erstes Zeichen $\land$, löscht dieses, geht nach rechts
  • $M'$ simuliert $M$
  • $\Rightarrow L(M') \neq L(M)$, weil jedes Wort $w \in L(M')$ mit $\land$ beginnt und damit $w \notin L(M)$
• $\text{enc}(M)\#\#\text{enc}(M') \in \neg P_\text{äquiv}$, da $L(M) \neq L(M')$

$P_\text{halt}$ ist nicht co-semi-entscheidbar
$\Rightarrow P_\text{äquiv}$ ist nicht co-semi-entscheidbar
$\Rightarrow \neg P_\text{äquiv}$ ist nicht semi-entscheidbar

$\neg P_\text{halt}$ ist nicht co-semi-entscheidbar
$\Rightarrow \neg P_\text{äquiv}$ ist nicht co-semi-entscheidbar
$\Rightarrow P_\text{äquiv}$ ist nicht semi-entscheidbar

4. Übungsblatt

Aufgabe H

Sei $L$ eine unentscheidbare Sprache. Zeigen Sie:
a) $L$ hat eine Teilmenge $T \subseteq L$, die entscheidbar ist.

$T = \emptyset$ mit Entscheider $M_T$: $M_T$ hat nur einen Zustand, der ein nicht-akzeptierender Endzustand ist.

Sei $L$ eine unentscheidbare Sprache. Zeigen Sie:
b) $L$ hat eine Obermenge $O \supseteq L$, die entscheidbar ist.

$O = \Sigma^{*}$ mit Entschieder $M_O$: $M_O$ hat nur einen Zustand, der ein akzeptierender Endzustand ist.

Sei $L$ eine unentscheidbare Sprache. Zeigen Sie:
c) Es gibt jeweils nicht nur eine sondern unendlich viele entscheidbare Teilmengen bzw. Obermengen wie in (a) und (b).

Jede überabzählbare Menge $L(M)$ hat unendlich viele abzählbare Teilmengen $T \subseteq L(M)$. Wenn $T$ abzählbar ist, dann ist $T$ entscheidbar.

$O = (\Sigma \cup \Sigma_{+})^{*}$ mit $\Sigma \cap \Sigma_{+} = \emptyset$ (Das Alphabet von $O$ wird um weitere Zeichen, die nicht in $\Sigma$ liegen, erweitert.): Es existieren unendlich viele $\Sigma_{+}$.

Aufgabe 4.1

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
a) Falls $\text{P} \neq \text{NP}$ gilt, dann auch $\text{P} \cap \text{NP} \neq \emptyset$

falsch, für eine deterministische Turing-Maschine in P lässt sich auch immer eine nicht-deterministische Turing-Maschine in NP konstruieren.

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
b) Es gibt Probleme, die NP-hard, aber nicht NP-vollständig sind.

wahr, Gegenbeispiel $P_\text{halt}$: Jedes Problem in NP kann auf $P_\text{halt}$ reduziert werden $\Rightarrow P_\text{halt} \in \text{NP-hard}$, aber $P_\text{halt} \notin \text{NP}$ (siehe Ackermann-Funktion, Busy-Beaver, …) und damit nicht NP-complete.

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
c) Polynomielle Reduzierbarkeit ist nicht transitiv.

falsch, Many-One-Reduktionen sind transitiv: aus $A \leq_m B$ mit $f_a : A \rightarrow B$ und $B \leq_m C$ mit $f_b : B \rightarrow C$ folgt $f_{a,b} : A \rightarrow C$ mit $f_{a,b}(x) := f_b(f_a(x))$. Eine polynomielle Reduktion ist eine Many-One-Reduktion mit polynomieller Laufzeit. Eine Verkettung von polynomiellen Funktion erzeugt auch wieder eine polynomielle Funktion.

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
d) Ist $L_2 \in \text{P}$ und $L_1 \leq_p L_2$, dann ist auch $L_1 \in \text{P}$.

wahr, für $L_2$ existiert eine deterministische Turing-Maschine mit polynomieller Laufzeit $M_2$ als Entscheider. Jedes Wort in $w_1$ in $L_1$ lässt sich entscheiden, indem man es mit einer Funktion $f$ in ein Wort $w_2$ in $L_2$ überführt und anschließend der Entscheider $M_2$ simuliert. Sowohl $f$ als auch $M_2$ laufen in polynomieller Zeit, also ist $L_1$ in P entscheidbar.

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
e) Ist $L_1$ eine NP-vollständige Sprache und gilt $L_1 \leq_p L_2$, dann ist auch $L_2$ eine NP-vollständige Sprache.

wahr, da $L_1$ polynomiell entscheidbar ist und $L_1$ mit einer polynomiellen Funktion in $L_2$ überführt werden kann, muss auch der Entscheider für $L_2$ ebenfalls polynomiell lange laufen. Damit liegt $L_2$ in NP. Da $L_1$ aber auch in NP-hard liegt, muss also auch $L_2$ in NP-hard liegen. Da $L_2$ in NP und NP-hard liegt, liegt es in NP-complete.

Welche der folgenden Aussagen sind wahr? Begründen Sie Ihre Antwort.
f) Ist $L_2$ eine NP-vollständige Sprache und gilt $L_1 \leq_p L2$, dann ist auch $L_1$ eine NP-vollständige Sprache.

falsch, $L_1 \in \text{NP} \setminus \text{NP-complete}$ ist möglich.

Gegenbeispiel:

• $L_2 = \text{SAT} \in \text{NP-complete}$
• $L_1 = \text{HORN-SAT} \in \text{P}$
• $L_1 \subseteq L_2 \Rightarrow$ Reduktion mit $O(1)$

Aufgabe 4.2

Zeigen Sie, dass das Wortproblem deterministischer endlicher Automaten in LogSpace liegt:
ist $P_\text{DFA} := \{\text{enc}(A)\#\#\text{enc}(w) | A$ ist ein DFA, der $w$ akzeptiert$\}$, dann gilt $P_\text{DFA} \in \text{LogSpace}$

Der Speicherbedarf ist mit $O(\log{\left| \text{enc}(A)\#\#\text{enc}(w) \right|})$ beschränkt. Der Automat ist wie folgt definiert $A = (Q, \Sigma, \delta, q_0, F)$. Um $P_\text{DFA}$ zu simulieren, muss die aktuelle Position in $w$ und der aktuelle Zustand von $A$ gespeichert werden. Da der Automat $A$ deterministisch ist, kann er sich immer nur in genau einem $q \in Q$ befinden. Also $i \in \{0, 1, \ldots, m - 1\}$ mit $Q = \{q_0, q_1, \ldots, q_{m - 1}\}$ und $j \in \{0, 1, \ldots, n - 1\}$ mit $w = w_0 w_1 \ldots w_{n - 1}$ zu speichern. Solange $i$ und $j$ nicht unär kodiert sind, ist $\left| i \right| \sim \log{i}$ mit $\left| i \right|$ als Länge der Kodierung der Zahl $i$.

Aufgabe 4.3

Wir betrachten das folgende Problem $K$: Gegeben sind zwei gerichtete Graphen $G_1 = (V_1, E_1)$ und $G_2 = (V_2, E_2)$ sowie eine Zahl $k \in N$. Gefragt ist, ob es Teilmengen $V_1' \subseteq V_1$ und $V_2' \subseteq V_2$ gibt, so dass $\left|V_1'\right| = \left|V_2'\right| = k$ ist und es eine Bijektion $f : V_1' \rightarrow V_2'$ gibt, so dass gilt
$(u, v) \in E_1 \Leftrightarrow (f(u), f(v)) \in E_2$.
a) Zeigen Sie $K \in \text{NP}$.

$K$ ermittelt, ob $G_1$ und $G_2$ isomorphe Subgraphen mit $k$ Knoten enthalten. $K \in \text{NP}$ genau dann, wenn eine Lösung $V_1'$, $V_2'$, $f$ in polynomieller Zeit überprüft werden kann:

def check(V1_, V2_, f):
    assert len(V1_) == len(V2_)
    for u in V1_:
        for v in V1_:
            u_v_in_E1 = False
            for e in E1:
                if (u, v) == e:
                    u_v_in_E1 = True
            if u_v_in_E1:

                u2 = f(u)
                u2_in_V2 = False
                for x in V2_:
                    if u2 == x:
                        u2_in_V2 = True
                assert u2_in_V2

                v2 = f(v)
                v2_in_V2 = False
                for x in V2_:
                    if v2 == x:
                        v2_in_V2 = True
                assert v2_in_V2

                u2_v2_in_E2 = False
                for e in E2:
                    if (u2, v2) == e:
                        u2_v2_in_E2 = True
                assert u2_v2_in_E2

check(V1_, V2_, f) hat eine Laufzeit $O(\left| V_1' \right|^2 (\left| E_1 \right| + 2(\left| f \right| + \left| V_2' \right|) + \left| E_2 \right|))$ mit $f$ der Laufzeit von $O(\left| V_1' \right| \cdot \left| V_2' \right|)$. Damit ist check(V1_, V2_, f) polynomiell. Überprüfung der Lösung ist in polynomieller Zeit möglich, damit ist $K \in \text{NP}$.

Wir betrachten das folgende Problem K: Gegeben sind zwei gerichtete Graphen $G_1 = (V_1, E_1)$ und $G_2 = (V_2, E_2)$ sowie eine Zahl $k \in N$. Gefragt ist, ob es Teilmengen $V_1' \subseteq V_1$ und $V_2' \subseteq V_2$ gibt, so dass $\left|V_1'\right| = \left|V_2'\right| = k$ ist und es eine Bijektion $f : V_1' \rightarrow V_2'$ gibt, so dass gilt
$(u, v) \in E_1 \Leftrightarrow (f(u), f(v)) \in E_2$.
b) Zeigen Sie, dass $K$ ein NP-schweres Problem ist. Zeigen Sie dafür, dass das Problem CLIQUE auf K in polynomieller Zeit reduzierbar ist.

CLIQUE sucht für einen ungerichteten Graph $G = (V, E)$ und $k \in \mathbb{N}$ einen Subgraph $G' = (V', E')$ mit $V' \subseteq V$, $\left| V' \right| = k$ und $E' := \{\{u, v\} | u, v \in V', u \neq v, \{u, v\} \in E\}$, so dass jeder Knoten des Subgraphs mit jedem anderen Knoten des Subgraphs verbunden ist.

$\text{CLIQUE} \leq_p K$:

• gegeben: ungerichteter Graph $G_\text{CLIQUE} = (V_\text{CLIQUE}, E_\text{CLIQUE})$ und $k_\text{CLIQUE} \in \mathbb{N}$
• $G_\text{CLIQUE}$ ist ungerichtet $\Rightarrow$ $E_\text{CLIQUE}^{\rightarrow} := \displaystyle \bigcup_{\{u,v\} \in E_\text{CLIQUE}} \{(u, v), (v, u)\}$ ($O(n)$)
• Führe $K$ aus:
  • $G_1 := (V_\text{CLIQUE}, E_\text{CLIQUE}^{\rightarrow})$ ($O(1)$)
  • $G_2 := (V_\text{CLIQUE}, E_\text{total})$ mit $E_\text{total} = \{(u, v) | u \in V, v \in V\}$ ($O(n^2)$)
  • $k := k_\text{CLIQUE}$ ($O(1)$)
  • $K \in \text{NP}$ sucht also einen Subgraph, der sowohl in $G_1$ als auch $G_2$ enthalten ist. (Da $V_1 = V_2 = V$ ist $f(x) = x$ und spart die Bijektion der Knoten.) Da in $G_2$ alle Knoten miteinander verbunden sind, ist der Subgraph nur in $G_1$ enthalten, wenn dort auch alle Knoten des Subgraphs miteinander verbunden sind.
  • Ergebnis: $G_1' = (V_1', E_1')$ mit $E_1' \subseteq E_\text{CLIQUE}^{\rightarrow}$, jeder Knoten in $V_1'$ ist mit jedem anderen Knoten in $V_1'$ verbunden
• CLIQUE ist auch wieder ein ungerichteter Graph, alss muss $E_1'$ noch umgewandelt werden, um die Lösung von CLIQUE zu erhalten: $\{\{u, v\} | (u, v) \in E_\text{CLIQUE}^{\rightarrow}\}$ ($O(n^2)$)

5. Übungsblatt

Aufgabe J

Zeigen Sie, dass NP unter Kleene-Stern abgeschlossen ist.

Es ist zu zeigen $\forall L \in \text{NP}: L^{*} \in \text{NP}$

gegeben: $M$ entscheidet in $O(p(\left| w \right|))$, ob $w \in L$ oder $w \notin L$

gesucht: nicht-deterministische Turing Maschine $M^{*}$, die in $O(p^{*}(\left| w \right|))$ entscheidet, ob $w \in L^{*}$ oder $w \notin L^{*}$

Beweis:

• nicht-deterministische Turing-Maschine $M^{*}$ rät Aufteilung von $w \in L^{*}$ in $w = w_1 w_2 \ldots w_n$ mit $w_k \in L$
  in $O(p_w(\left| w \right|))$ überprüfbar
• $M^{*}$ akzeptiert das leere Wort $\varepsilon$
• $M^{*}$ simuliert $M$ für jedes $w_k$ in $O(p(\left| w_1 \right|) + \ldots + p(\left| w_n \right|))$
  • akzeptiert $M$ jedes $w_k$ $\Rightarrow M^{*}$ akzeptiert
  • sonst $M^{*}$ lehnt ab

Aufgabe 5.1

Wir betrachten das folgende Problem $K$: Gegeben eine aussagenlogische Formel $\varphi$ mit $n$ Variablen, gibt es eine erfüllende Belegung von $\varphi$, bei der mindestens die Hälfte aller in $\varphi$ vorkommenden Variablen mit “true” belegt sind?
a) Formalisieren Sie dieses Problem als Sprache und zeigen Sie, dass $K \in \text{NP}$ gilt.

$L_K := \left\{ (\varphi, b) | \text{$b$ ist eine Belegung der aussagenlogische Formel bei der mindestens die Hälfte aller in $\varphi$ vorkommenden Variablen mit *"true"* belegt sind} \right\}$

nicht-deterministische Turing-Maschine:

• rät $(\varphi, b)$
• prüft in polynomieller Zeit, ob $\varphi$ erfüllt ist
• prüft in polynomieller Zeit, ob mindestens die Hälfte aller in $\varphi$ vorkommenden Variablen mit “true” belegt sind

Wir betrachten das folgende Problem $K$: Gegeben eine aussagenlogische Formel $\varphi$ mit $n$ Variablen, gibt es eine erfüllende Belegung von $\varphi$, bei der mindestens die Hälfte aller in $\varphi$ vorkommenden Variablen mit “true” belegt sind?
b) Zeigen Sie, dass K ein NP-schweres Problem ist.

$P_\text{SAT} \leq_m K$ ($P_\text{SAT} \in \text{NP-complete} \subseteq \text{NP-hard}$), Reduktionsfunktion:

• Eingabe $\text{enc}(\varphi, b) \in P_\text{SAT}$ mit $b = (b_1, b_2, \ldots, b_{\left| b \right|})$
• erweitere $\varphi$ um $\left| b \right|$ weitere Variablen, die alle mit “true” belegt sein müssen:
  • $\varphi_K := \varphi \land \displaystyle \bigwedge_{i = 1}^{\left| b \right|} a_i = \varphi \land a_1 \land \ldots \land a_{\left| b \right|}$
  • $b_K := (b_1, b_2, \ldots, b_{\left| b \right|}, a_1 \mapsto \top, a_2 \mapsto \top, \ldots, a_{\left| b \right|} = \top)$
    $\Rightarrow$ die Hälfte aller Variablen in $b_K$ ist mit $\top$ belegt
• $\Rightarrow \text{enc}(\varphi_k, b_K) \in K$
• Da $K \in \text{NP-hard}$ und nicht $K \in \text{NP-complete}$ gefragt war, ist die Laufzeit der Reduktion egal, wird wohl aber doch polynomiell sein.

Aufgabe 5.2

Im folgenden Solitaire-Spiel haben wir ein Spielbrett der Größe $m \times m$ gegeben. Als Ausgangsposition liegt auf jeder der $m^2$ Positionen entweder ein blauer Stein, ein roter Stein, oder gar nichts. Das Spiel wird nun so gespielt, dass Steine vom Brett genommen werden bis in jeder Spalte nur noch Steine einer Farbe liegen, und in jeder Zeile mindestens ein Stein liegen bleibt. In diesem Fall ist das Spiel gewonnen. Es ist möglich, dass man ausgehend von einer Ausgangsposition das Spiel nicht gewinnen kann.
a) Formalisieren Sie das Problem, für eine gegebene Ausgangsposition im Solitaire-Spiel zu entscheiden, ob es möglich ist, das Spiel zu gewinnen, als ein Entscheidungsproblem SOLITAIRE.

$P_\text{SOLITAIRE} = \left\{ \text{enc}(B) | \text{$B$ ist eine Ausgangsposition, die gewonnen werden kann} \right\}$

Im folgenden Solitaire-Spiel haben wir ein Spielbrett der Größe $m \times m$ gegeben. Als Ausgangsposition liegt auf jeder der $m^2$ Positionen entweder ein blauer Stein, ein roter Stein, oder gar nichts. Das Spiel wird nun so gespielt, dass Steine vom Brett genommen werden bis in jeder Spalte nur noch Steine einer Farbe liegen, und in jeder Zeile mindestens ein Stein liegen bleibt. In diesem Fall ist das Spiel gewonnen. Es ist möglich, dass man ausgehend von einer Ausgangsposition das Spiel nicht gewinnen kann.
b) Zeigen Sie, dass $\text{SOLITAIRE} \in \text{NP}$ gilt.

nicht-deterministische Turing-Maschine:

• Rät ausgehend vom Ausgangsbrett eine erfüllende End-Position.
• Falls keine Endposition existiert, dann akzeptiere nicht.
• Prüfe für jede der $m$ Spalten, ob alle Steine die gleiche Farbe haben. $O(m^2)$
• Prüfe für jede der $m$ Zeilen, ob diese mindestens einen Stein enthält. $O(m^2)$
• In $O(m^2)$ Schritten lässt sich aus der Endposition das Ausgangsbrett wiederherstellen, indem die Steine, so wie sie auf dem Ausgangsbrett lagen, wieder zur Endposition hinzugefügt werden ohne bereits liegende Steine zu ersetzen.

Für eine gegebene Endposition lässt sich also in $O(m^2)$ überprüfen, ob diese zu der Ausgangsposition passt $\Rightarrow P_\text{SOLITAIR} \in \text{NP}$

Im folgenden Solitaire-Spiel haben wir ein Spielbrett der Größe $m \times m$ gegeben. Als Ausgangsposition liegt auf jeder der $m^2$ Positionen entweder ein blauer Stein, ein roter Stein, oder gar nichts. Das Spiel wird nun so gespielt, dass Steine vom Brett genommen werden bis in jeder Spalte nur noch Steine einer Farbe liegen, und in jeder Zeile mindestens ein Stein liegen bleibt. In diesem Fall ist das Spiel gewonnen. Es ist möglich, dass man ausgehend von einer Ausgangsposition das Spiel nicht gewinnen kann.
c) Zeigen Sie, dass SOLITAIRE ein NP-schweres Problem ist, indem Sie zeigen, dass 3-SAT in polynomieller Zeit auf SOLITAIRE reduzierbar ist.

$P_\text{3-SAT} \leq_p P_\text{SOLITAIRE}$ TODO

Aufgabe 5.3

Sei $\Sigma$ ein Alphabet und $A, B \subseteq \Sigma^{*}$. Wir sagen, dass $A$ auf $B$ in logarithmischen Platz reduzierbar ist, und schreiben $A \leq_\ell B$, falls es eine Many-One-Reduktion von $A$ nach $B$ gibt, die in logarithmischen Platz berechenbar ist. Begründen Sie: Gilt $A \leq_\ell B$ und $B \leq_\ell C$, dann gilt auch $A \leq_\ell C$.
Anmerkung: Bei dieser Aufgabe ist nicht nach einem vollständigen Beweis, sondern eher nach einer Beweisidee gefragt.

Problem: lediglich das Arbeitsband der Reduktion $g$ bzw. $M_g$ ist mit $O(\log{n})$ beschränkt, die Ausgabe von $g$ bzw. $M_g$ kann aber $O(p(n))$ sein.

Musterlösung

Wir zeigen, dass für zwei logspace-berechenbare Funktion $f, g\colon \Sigma^{*} \to \Sigma^{*}$ auch $f \circ g$ logspace-berechenbar ist. Seien dazu $M_{f}$ und $M_{g}$ Turing-Maschinen, die mit logarithmischer Platzbeschränkung die Funktionen $f$ und $g$ berechnen.

Eine erste Idee, eine Turing-Maschine $M$ zu erhalten, die $f \circ g$ berechnet, ist, zuerst $M_{g}$ auf der Eingabe aufzurufen, das Zwischenergebnis zu speichern, und dann $M_{f}$ auf diesem Zwischenergebnis laufen zu lassen. Diese Idee funktioniert jedoch nicht: zwar benutzt $M_{g}$ bei Eingabe $w \in \Sigma^{*}$ nur zusätzlich logarithmischen Platz zur Berechnung von $g(w)$. Dieses Ergebnis kann jedoch polynomiell groß sein in der Länge von $w$ – und damit exponentiell in der Größe des zur Verfügung stehenden Platzes, der ja logarithmisch in der Größe von $w$ beschränkt ist. Damit kann das Zwischenergebnis $g(w)$ nicht vollständig gespeichert werden und dieser Ansatz funktioniert nicht.

Wir können aber diese Idee so modifizieren, dass sie funktioniert! Dazu berechnen wir die Zeichen von $g(w)$ “on demand”: wir verändern $M_{g}$ so, dass sie nur das $k$-te Symbol von $g(w)$ berechnet. Dies kann erreicht werden, indem $M_{g}$ mit einem weiteren Zähler $p$ versehen wird, der um eins hochgezählt wird, wann immer $M_{g}$ ein Symbol ausgeben möchte. Ist der Wert von $p$ gleich $k$, gibt $M_{g}$ das entsprechende Zeichen aus und hält an.

Um $f(g(w))$ in LogSpace zu berechnen, gehen wir nun wie folgt vor: wir simulieren die Berechnung von $M_{f}$. Wann immer diese Berechnung ein Symbol von $g(w)$ lesen möchte, simulieren wir $M_{g}$ wie oben beschrieben. Beide Simulationen können in logspace durchgeführt werden, und damit kann auch $f(g(w))$ in logspace berechnet werden.

Diese Berechnung von $f(g(w))$ ist recht ineffizient, da Symbole von $g(w)$ möglicherweise mehrfach berechnet werden. Wir haben aber potentiell nicht genug Platz, um das gesamte Wort $g(w)$ zu speichern. Wir tauschen also “Platz gegen Zeit”.

Aufgabe 5.4

PCP-k ist das folgende Entscheidungsproblem:
Gegeben: eine Zahl $k \in \mathbb{N}$ in unärer Kodierung und eine Instanz $P$ des Postschen Korrespondenzproblems, d.h. eine endliche Folge von Wortpaaren $$P = (x_1, x_2), \ldots, (x_n, y_n)$$ über einem Alphabet $\Sigma$, also $x_i, y_i \in \Sigma^{+}$ für $1 \leq i \leq n$.
Gefragt: Gibt es eine Lösung für $P$ mit maximaler Länge $k$? Oder genauer: Gibt es eine Folge von Zahlen $i_1, \ldots, i_\ell$, so dass gilt: $$x_{i_1} \ldots x_{i_\ell} = y_{i_1} \ldots y_{i_\ell}$$ wobei $0 < \ell \leq k$ ist und $i_j \in \{1, \ldots, n\}$ für alle $j = 1, \ldots, \ell$?
a) Zeigen Sie, dass PCP-k entscheidbar ist.