\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage{cancel}
\usepackage{eurosym}

\thispagestyle{empty}

\title{Theoretische Informatik (WS 2005/2006) - Übungsblatt 9}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Do, 11-13 Uhr, Vasileios Anastasatos
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\B}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\eur}{\mbox{\euro}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage
\section*{Aufgabe 1}
Es sei $\Sigma = \{0,1,\$\}$. Wir betrachten
$$L = \{u \$ v | u \in SAM \mbox{ und } v \in \overline{SAM}\}$$
Weder $L$ noch $\overline{L}$ sind akzeptierbar.
\begin{itemize}
	\item Zu zeigen: $\overline{SAM} \preceq L$. \\
		Dazu konstruieren wir eine TM-berechenbare Funktion $f: \Sigma^* \to \Sigma^*$ mit $x \in \overline{SAM} \Leftrightarrow f(x) \in L$. \\
		Es sei nun $M_1$ Turing-Maschine mit $M_1 \in SAM$. \\
		Wir setzen $f(x) = \left< M_1 \right>\$ x$. Dann gilt:
		\begin{align*}
			x \in \overline{SAM} & \Rightarrow f(x) = \left< M_1 \right> \$ x \in L \\
			x \notin \overline{SAM} & \Rightarrow x \in SAM \Rightarrow f(x) = \left< M_1 \right> \$ x \notin L
		\end{align*}
		Aus der Vorlesung wissen wir, dass $\overline{SAM}$ nicht akzeptierbar ist. Mit der Behauptung
		$$L_1 \preceq L_2 \mbox{ und } L_1 \mbox{ nicht akzeptierbar } \Rightarrow L_2 \mbox{ nicht akzeptierbar}$$
		sehen wir, dass $L$ nicht akzeptierbar ist.
	\item Zu zeigen: $\overline{SAM} \preceq \overline{L}$. \\
		Dazu konstruieren wir eine Turing-Maschine $M_2 \notin SAM$. Wir setzen $f(x) = x \$ \left< M_2 \right>$. Dann gilt:
		\begin{align*}
			x \in \overline{SAM} & \Rightarrow f(x) = x \$ \left< M_2 \right> \notin L \Rightarrow f(x) \in \overline{L} \\
			x \notin \overline{SAM} & \Rightarrow x \in SAM \Rightarrow f(x) = x \$ \left< M_2 \right> \in L \Rightarrow f(x) \notin \overline{L}
		\end{align*}
		Wie oben folgt, dass $\overline{L}$ nicht akzeptierbar ist.
\end{itemize}

Zeige, dass gilt:
\begin{itemize}
	\item $L_1 \preceq L_2$ und $L_2$ akzeptierbar $\Rightarrow L_1$ akzeptierbar \\
		$L_2$ sei akzeptierbar, d.h. es gibt eine Turing-Maschine $M_2$, die $L_2$ akzeptiert. $L_1 \preceq L_2$ bedeutet, dass es eine berechenbare Funktion $f$ gibt mit $x \in L_1 \Leftrightarrow f(x) \in L_2$. Diese werde realisiert durch die Turing-Maschine $M_1$. Wir konstruieren daraus eine Turing-Maschine $M$, die $L_1$ akzeptiert. Es sei eine Eingabe $x$ gegeben. Zuerst simuliert $M$ die Maschine $M_1$ und berechnet $f(x)$ ($M_1$ terminiert für alle $x \in L_1$), danach simuliert sie $M_2$ bei Eingabe $f(x)$. Sie akzeptiert $f(x)$ genau dann, wenn $f(x) \in L_2$ ist, was gleichbedeutend mit $x \in L_1$ ist. Also akzeptiert $M$ eine Eingabe $x$ genau dann, wenn $x \in L_1$.
	\item $L_1 \preceq L_2$ und $L_1$ nicht akzeptierbar $\Rightarrow L_2$ nicht akzeptierbar \\
		Nehmen wir an, $L_2$ wäre akzeptierbar. Dann folgt aus obiger Implikation, dass $L_1$ akzeptierbar wäre, was aber der Voraussetzung widerspricht.
\end{itemize}

\section*{Aufgabe 2}
\subsubsection*{(a)}
Eine BB-TM kann die Sprache $\overline{\mbox{\textsf{UNIV}}}$ akzeptieren, indem das Ergebnis invertiert wird, d.h., sagt die BB-TM für \textsf{UNIV} ja (ist also in Zustand $q_{ja}$), dann sagt die BB-TM für $\overline{\mbox{\textsf{UNIV}}}$ nein (ist also im Zustand $q_{nein}$) und umgekehrt.

\subsubsection*{(b)}

\section*{Aufgabe 3}
\subsubsection*{(a)}
\textbf{Idee:} Das Problem ist entscheidbar. \\[0.5cm]
Sei $(x_i,y_i)$ für $i=1,...,n$ eine Instanz des \textsf{PCP}$_\Sigma$. Die Frage, ob es eine Indexfolge $(i_1,...i_k)$ mit $k \in \SetN, i_1,...,i_k \in \{1,...,n\}$ mit $x_{i_1},...,x_{i_k} = y_{i_1},...,y_{i_k}$ gibt, ist äquivalent zu der Frage, ob es eine Indexfolge $(i_1,...,i_k)$ gibt mit
\begin{align*}
|x_{i_1} ... x_{i_k}| &= |y_{i_1} ... y_{i_k}| \\
&= |x_{i_1}| + ... + |x_{i_k}| \\
&= |y_{i_1}| + ... + |y_{i_k}|
\end{align*}
Dann gilt:
$$\mbox{\textsf{PCP}}_\Sigma \mbox{ unlösbar } \Leftrightarrow \forall i: |x_i| < |y_i| \mbox{ oder } \forall i: |y_i| < |x_i|$$
\begin{itemize}
	\item $\Rightarrow$:\\ Sei \textsf{PCP}$_\Sigma$ unlösbar. Falls es ein $(x_i,x_j)$ mit $|x_i| = |x_j|$ gibt, dann besitzt \textsf{PCP}$_\Sigma$ eine Lösung (Widerspruch zur Annahme). Es gelte deshalb nun $|x_i| \neq |y_i| \; \forall i$. Wir nehmen an, dass es ein $j$ und ein $k$ gibt mit $|x_j| > |y_j|, |x_k| < |y_k|$. Betrachte dazu
	\begin{align*}
		n_1 &:= |x_j| - |y_j| \\
		n_2 &:= |y_k| - |x_k|
	\end{align*}
	Es gilt nun:
	\begin{align*}
		|x_j^{n_2}x_k^{n_1}| &= (n_1 + |y_j|) \cdot n_2 + (|y_k| - n_2) \cdot n_1 \\
		&= n_2 \cdot |y_j| + n_1 \cdot |y_k| \\
		&= |y_j^{n_2}y_k^{n_1}|
	\end{align*}
	Es gilt, dass $j^{n_2} \cdot k^{n_1}$ eine Lösung des \textsf{PCP}$_\Sigma$ ist.
	
	\item $\Leftarrow$:\\ Sei nun $|x_i| < |y_i| \; \forall i$. Dann gilt $\forall(i_1,...,i_k), k \ge 1$:
	\begin{align*}
		|x_{i_1} ... x_{i_k}| &= |x_{i_1}| + ... + |x_{i_k}| \\
		&< |y_{i_1}| + ... + |y_{i_k}| \\
		&= |y_{i_1} ... y_{i_k}|
	\end{align*}
	Also kann es keine nichttriviale Lösung geben.
\end{itemize}
$\Longrightarrow$ Um \textsf{PCP}$_\Sigma$ zu entscheiden, genügt es $|y_i| < |x_i|$ für alle $i$ zu testen.

\subsubsection*{(b)}
\textbf{Idee:} Das Problem ist entscheidbar. \\[0.5cm]
Sei $|\Sigma| = 3$; $0 < |x_i| \leq 5$. \\
Auf einer Kartenhälfte können nur $\underbrace{3}_{|x_i|=1} + \underbrace{3^2}_{|x_i|=2} + \underbrace{3^3}_{|x_i|=3} + \underbrace{3^4}_{|x_i|=4} + \underbrace{3^5}_{|x_i|=5} = 363$ verschiedene Strings stehen.
Es gibt nur $363^2$ verschiedene Karten.
Es gilt: $k \leq 363^2$, denn es kann nicht mehr verschiedene Karten geben, als es überhaupt Karten geben kann.
Für ein $k$ gibt es nur endlich viele Instanzen des \textsf{PCP} mit $k$ Spielkarten, genauer ${363^2 \choose k}$.
Die Summe aller Instanzen ist $\sum_{k=0}^{363^2} {363^2 \choose k}$, was wiederum endlich ist.
Die Gesamtzahl aller Instanzen ist gerade $2^{(363^2)}$, dies ist nämlich die Mächtigkeit der Potenzmenge einer $363^2$-elementigen Menge.
Um eine endliche Menge zu entscheiden, genügt ein endlicher Automat. Ein endlicher Automat kann von einer Turing-Maschine simuliert werden.
Reguläre Sprachen sind unter Komplementbildung abgeschlossen.
Das Problem ist also entscheidbar.

\end{document}