\documentclass[10pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath, amsfonts, amsthm, amssymb}
\usepackage[dutch]{babel}
\usepackage{fullpage}
\title{Opgave red2-22}

\author{J.M. Vuong \and R. Ros}
\date{05/28/2007}
\begin{document}
	\maketitle
	\subsection*{Probleem}
		Ga na of het volgende probleem beslisbaar danwel onbeslisbaar is.\\

		“Gegeven een willekeurige Turing-machine $M$ , bevat de taal $L(M)$ van alle strings die door $M$ worden geaccepteerd, een string met lengte 5?”
	\subsection*{Bewijs}
        Het probleem ($D$) bevat alle coderingen van Turingmachines $M$ die talen herkennen waarin tenminste 1 woord van lengte 5 zit. \\

        \noindent Het is duidelijk dat er een TM $M_5$ bestaat die de taal $L(M_5)$, bestaande uit alleen woorden met lengte 5, beslist. Bijvoorbeeld : \\

        \noindent $M_5$ = "Op invoer $y$:\\
              \indent 1. Als $|y|$ = 5, \textit{accepteer}, anders \textit{verwerp}"\\

        \noindent Voor deze Turingmachine geldt evident $<M_5> \in D$\\

        \noindent We voeren de reductie : $HALT_{tm} \leq _{m}D$ uit.\\

        \noindent Er moet dus een reductiefunctie $f$ gevonden worden die een instantie $<M,w> \in HALT_{tm}$ afbeeldt op een instantie $<M'> \in D$, z.d.d. $<M,w> \in HALT_{tm}$ desda $<M'> \in D$. $M'$ kan dan als volgt worden gedefineerd:\\

        \noindent $M'$ = "Op invoer $x$:\\
        	\indent 1. Draai $M$ op invoer $w$\\
        	\indent 2. Draai $M_5$ op invoer $x$\\
        	\indent 3. Geef terug wat stap 2 deed"\\

        \noindent De functie $f$ wordt door de volgende TM $F$ berekend:\\

        \noindent $F$ = "Op invoer $<M,w>$:\\
        	\indent 1. Construeer $M'$\\
        	\indent 2. Retourneer $<M'>$"\\

        \noindent $f$ is dus een berekenbare functie.\\

        \noindent Nu moet er bewezen worden dat $f$ aan de mapping reduction eis voldoet. Dit gaat als volgt:\\

        \indent 1. Als $<M,w> \in HALT_{tm}$ dan zal stap 1 in $M'$ termineren. Vervolgens worden stappen 2 en 3 uitgevoerd. Dit betekent dat $M'$ zich zal gedragen als $M_5$, en zoals eerder is vermeldt geldt : $<M_5> \in D$\\

        \indent 2. Als $<M,w> \notin HALT_{tm}$, dan zal $M$ dus niet termineren op invoer $w$ en zullen stappen 2 en 3 niet bereikt worden. Dit betekent dat $M'$ voor geen enkele invoer $x$ zal termineren, dus $L(M') = \emtpyvar$. Dus $<M'> \notin D$.

        \noindent Hiermee is aangetoond dat $f$ aan de eisen van een mapping reduction voldoet. M.a.w. $f$ is een reductie van $HALT_{tm}$ naar $D$.
\end{document}