\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor,multicol}
\usepackage{varwidth, hyperref}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\st}{~\mid~}
\name{** UPDATED May 18 **}
\class{CSE 105}
\assignment{Homework 6}
\duedate{Due: Sunday May 21, 2017}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
Upload a {\bf single file} to Gradescope for each group.
All group members' names and PIDs
should be on {\bf each} page of the submission.\\
Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound. \\
{\sc Reading} Sipser Sections 3.1, 3.2, 3.3, 4.1
\newline
{\sc Key Concepts} TM variants, Church-Turing thesis, decidable
languages, decidable problems.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 9 points})
\begin{itemize}
\item[(a)] Prove that each Turing machine can be converted to a
(potentially different) Turing machine that recognizes the same language
but never rejects. In other words, on each input string, this new machine
will either accept or loop.
{\it Your proof should give and justify the formal definition of new Turing machine
based on parameters describing the old machine.}
\item[(b)] Explain why there's no such conversion procedure that'd
always produce a Turing machine that, on each input string, will
either accept or reject (but never loop).
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 8 points})
Give an implementation level description of a Turing
machine deciding the set $\{ w w~|~ w \in \{0,1\}^* \}$.
Justify why your machine is a decider and why it
recognizes this language.
{\it Hint: how would you modify the construction on page 167?
Recall that Turing machines are defined to be deterministic.}
\end{problem}
\begin{problem}[3.]({\bf 8 points}) ** UPDATED May 18 ** Suppose $A$ is a
Turing-recognizable language over $\Sigma = \{0,1\}$
and that $M$ is a TM with $L(M) = A$.
Give a high-level description
of a Turing machine recognizing the set
$\{ u \# v ~|~ u \in A, v \in A\}$.
Justify why your machine recognizes this language. Is it a decider?
Why or why not?
\end{problem}
\begin{problem}[4.]({\bf 10 points}) ** UPDATED May 18 ** Prove that a language is decidable
if and only if some enumerator enumerates the language in the standard string order.
\end{problem}
\end{document}