\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 8}
\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}
Zu zeigen: $A$ entscheidbar $\Leftrightarrow A$ lexikographisch rekursiv aufzählbar.
\begin{itemize}
	\item {\bfseries $A$ entscheidbar $\Rightarrow A$ lexikographisch rekursiv aufzählbar.} \\
	$A$ entscheidbar $\Leftrightarrow \exists$ TM $M$: $M$ hält $\forall x \in A$ mit $\begin{cases}0, & x \notin A \\ 1, & x \in A\end{cases}$.
	\begin{itemize}
		\item Annahme: $A$ ist endlich. Dieser Fall ist trivial. $\checkmark$
		\item Annahme: $A$ ist unendlich:
			$\Sigma$ ist endlich, also insbesondere aufzählbar, somit o.B.d.A. auch lexikographisch aufzählbar. \\
			Sei nun $M'$ eine 3TM, die folgendermaßen aufgebaut ist: \\
			Auf Band 1 stehe unär kodiert ein $n \in \SetN$ \\
			Band 2 und Band 3 seien initial leer \\
			Programm: \\
			{\ttfamily simuliere} \\
			{\ttfamily \phantom{xxx} wenn Band 2 leer,} \\
			{\ttfamily \phantom{xxxxxx} für alle $w \in \Sigma$ aufsteigend} \\
			{\ttfamily \phantom{xxxxxxxxx} P (mit $v=\varepsilon$)} \\
			{\ttfamily \phantom{xxx} sonst für jedes Element $v$ von Band 2} \\
			{\ttfamily \phantom{xxxxxx} für alle $w \in \Sigma$ aufsteigend} \\
			{\ttfamily \phantom{xxxxxxxxx} P} \\
			{\ttfamily \phantom{xxx} kopiere Band 3 auf Band 2 (überschreibe dabei Band 2)} \\
			{\ttfamily \phantom{xxx} lösche Band 3} \\
			{\ttfamily bis auf weiteres}
		\item Mit {\ttfamily P}: \\
			{\ttfamily baue Wort $wv$} \\
			{\ttfamily wenn $M$ auf $wv$ mit 1 hält, lösche ein Element von Band 1} \\
			{\ttfamily schreibe $wv$ zu allen andern auf Band 3} \\
			{\ttfamily wenn Band 1 leer ist, halte mit $wv$}
	\end{itemize}
	$M'$ liefert jetzt das in lexikographischer Aufzählung $n$-te Element, berechnet also $G$, $G$ ist also berechenbar, damit ist $A$ lexikographisch rekursiv aufzählbar.
	
	\item {\bfseries $A$ lexikographisch rekursiv aufzählbar $\Rightarrow A$ entscheidbar.} \\
	Sei $M$ eine TM, die $G$ berechnet. Da es sich bei den Fällen endlicher $A$ um Spezialfälle handelt, berechnet $M$ o.B.d.A. auch diese. $\forall x \in A$ gilt: $\exists n \in \SetN: G(n) = x$, $M$ berechnet also $x$ aus der Eingabe $n$. \\
	Außerdem gilt $\forall x \in A: x$ ist endlich, also $\exists$ TM $M'$, die für eine Eingabe $\left< x,y\right> \in A \times A$ ausgibt, ob $x>y$ (Ausgabe 1) oder nicht (Ausgabe 0). Sie vergleicht nämlich o.B.d.A. für $x = \left<x_1,x_2,...,x_n\right>$ und o.B.d.A. für $y = \left<y_1,y_2,...,y_n\right>$ jeweils $x_1$ mit $y_1$ usw. bis sie eine Abweichung in $i \in \SetN$ feststellt und gibt $x_i > y_i$ aus. \\
	Sei nun $M''$ eine weitere TM die wie folgt aufgebaut ist: \\
	Band 1 enthalte initial 1 in geeigneter Form \\
	Band 2 enthalte $x$ \\
	Programm: \\
	{\ttfamily simuliere} \\
	{\ttfamily \phantom{xxx} wenn die Ausgabe von $M$ auf Band 1 mit Band 2 übereinstimmt, gib \verb!"!1\verb!"! aus} \\
	{\ttfamily \phantom{xxx} sonst addiere 1 zu Band 1 und schreibe das Ergebnis wieder auf Band 1} \\
	{\ttfamily bis $M'$ mit ($M$ auf Band 1) und Band 2 \verb!"!1\verb!"! ergibt} \\
	{\ttfamily in dem Fall halte mit \verb!"!0\verb!"!} \\
	$M''$ berechnet $\chi_a$, die charakteristische Funktion. Somit ist $A$ entscheidbar.
\end{itemize} \QED

\section*{Aufgabe 2}
Seien die Sprachen $A \subset \Sigma^*$, $B \subset \Gamma^*$ und $C \subset \Lambda^*$ gegeben. Seien weiterhin $A \preceq B$ und $B \preceq C$. Dann existieren total berechenbaren Funktionen $f: \Sigma^* \to \Gamma^*$ und $g: \Gamma^* \to \Lambda^*$ mit den Eigenschaften $x \in A \Leftrightarrow f(x) \in B$ und $y \in B \Leftrightarrow g(y) \in C$. Es wird nun eine Funktion $h$ definiert, die die Verknüpfung der Funktionen $f$ und $g$ darstellt: $h: \Sigma^* \to \Lambda^*; h \mapsto f \circ g$. Sie ist (ebenfalls) total berechenbar. Ohne Beschränkung der Allgemeinheit nehme ich an, dass die Turing-Maschine $M$ die Funktion $f$ und die Turing-Maschine $M'$ die Funktion $g$ berechnet. Die Funktion $h = f \circ g$ wird nun durch eine Turing-Maschine berechnet, die bei jeder Eingabe zuerst $M$ simuliert, bis $M$ in einen Haltezustand gelangen würde. Auf dem Zwischenergebnis wird jedoch durch Simulation von $M'$ weitergearbeitet. \\
Basierend auf den obigen Beobachtungen gilt nun folgendes:
$$x \in A \Leftrightarrow f(x) \in B \Leftrightarrow \underbrace{g(f(x))}_{=h(x)} \in C$$
Somit ist $A$ also auf $C$ reduzierbar ($A \preceq C$) und die Relation ist transitiv. \QED

\section*{Aufgabe 3}
\subsubsection*{(a)}
\textbf{Idee:} nicht entscheidbar. \\
\textbf{Sprache:} \\
$L_a = \{w \$ q \$ x \in \{0,1\}^* \$ \{0,1\}^* \$ \{0,1\}^* | M_w \mbox{ erreicht Zustand } decod(q) \mbox{ bei Eingabe } decod(x)\}$ \\
\textbf{Beweis:} \\
Sei o.B.d.A. $q$ der einzige Endzustand der TM, weiterhin $w:=cod(M)$. Genau dann, wenn $M$ $q$ erreicht, also $x$ akzeptiert und auf dieser Eingabe terminiert, ist $w \$ x \in UNIV$. \\
Somit ist das Problem genau dann entscheidbar, wenn $UNIV$ entscheidbar ist. $UNIV$ ist aber nicht entscheidbar. \QED

\subsubsection*{(b)}
\textbf{Idee:} entscheidbar. \\
\textbf{Sprache:} \\
$L_b = \{w \$ x \in \{0,1\}^* \$ \{0,1\}^* | M_w \mbox{ macht bei Eingabe } decod(x) \mbox{ mind. eine Kopfbewegung nach links}\}$ \\
\textbf{Beweis:} \\
Man betrachte o.B.d.A. eine ETM; im Fall einer $k$-Band TM kommt eine äquivalente ETM ohnehin nicht ohne Linksschritte aus, sofern die zu verwendeten Zellen aller Bänder konkateniert nicht ein exaktes Abbild des ETM-Bandes darstellen. \\
Angenommen, $M$ terminiert. In dem Fall ist das Problem entscheidbar (man simuliert einfach alle Schritte durch). Divergiert $M$, dann muss die Divergenz durch eine Schleife ohne gleichzeitige Abarbeitung des Bandes begründet sein, wenn nicht durch Linksschritte. Umgekehrt bedeutet das: entfernt man alle diese Schleifen, dann muss $M$ über $x$ terminieren, ansonsten macht sie Linksschritte. \\
Diese Schleifen zu erkennen, ist aber trivial, indem man eine zweite TM baut, die erkennt, wenn man zu einem Zustand zurückkehrt, ohne in der Zwischenzeit den Kopf bewegt zu haben. \\
Bei jeder Kopfbewegung von $M$ wird der \glqq Trace\grqq\ gelöscht. Kommt ein Zustand, der schon im Trace steht, nochmal vor, wird der Zyklus deaktiviert. \QED

\subsubsection*{(c)}
\textbf{Idee:} nicht entscheidbar. \\
\textbf{Sprache:} \\
$L_c = \{w | u \in L(M_w) \forall u \in \overline{L(M')}\}$ \\
\textbf{Beweis:} \\
Nach der Vorlesung sind Sprachen der Art $\{w | x \in L(M_w)\}$ nicht entscheidbar (Satz von Rice), insbesondere also nicht $L$. \QED

\end{document}