\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}