\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor}
\usepackage{varwidth, multicol}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\blank}{\textvisiblespace}
\newcommand{\st}{~\mid~}
\name{}
\class{CSE 105}
\assignment{Group Homework 6}
\duedate{Due: Saturday March 10, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
{\bf One member} of the group should upload your group submission to Gradescope.
During the submission process, they will be prompted to add the names of the rest
of the group members.
All group members' names and PIDs
should be on {\bf each} page of the submission.\\
Your homework must be typed. 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.\\
{\sc Reading} Sipser Sipser Sections 3.2, 3.3, 4.1
\newline
{\sc Key Concepts} Variants of Turing Machines, computational
problems, decidable problems.\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.]{\bf (10 points)}
A return-tape Turing machine is a variant of a Turing machine whose transitions
use the directions RIGHT and RETURN instead of RIGHT and LEFT. RIGHT moves the tape head one character to the right and RETURN returns the tape head to the beginning of the input. All other aspects of the formal definition
of a Turing machine in this model remain the same. \\
Prove that any language recognized by a return-tape Turing machine is Turing-recognizable, using an ordinary Turing machine to simulate the return-tape Turing machine.
\end{problem}
\begin{problem}[2.] {\bf (10 points)} Consider the following computational
problems:
\begin{itemize}
\item[] $EQ_{DFA} = \{ \langle A, B \rangle \st \text{$A$ and $B$ are DFAs and
$L(A) = L(B)$} \}$
\item[] $SUB_{DFA} = \{ \langle A, B \rangle \st \text{$A$ and $B$ are DFAs and
$L(A) \subseteq L(B)$} \}$
\item[] $DISJ_{DFA} = \{ \langle A, B \rangle \st \text{$A$ and $B$ are DFAs and
$L(A) \cap L(B) = \emptyset$} \} $.
\end{itemize}
Prove that $SUB_{DFA}$ and $DISJ_{DFA}$ are each Turing-decidable.
{\it You may (and should) use high-level descriptions of any Turing machines
you define. Make sure to provide both a machine definition and a proof
of correctness.}
\end{problem}
\begin{problem}[3.] {\bf (10 points)} We have seen
that $A_{TM}, E_{TM}, EQ_{TM}$, etc.\ are all undecidable problems.
Give an example of
a nonempty computational problem about Turing machines that {\bf is} decidable.
In other words, fill in the blanks below:
\[
\{ \langle M \rangle \st \text{$M$ is a Turing machine and \ldots } \}
\]
and prove that the resulting language is Turing-decidable.
\end{problem}
\end{document}