\documentclass{article}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{fullpage}
\usepackage{eucal}
\usepackage{graphicx}
\usepackage{color}
\usepackage{tikz}
\usepackage{algorithm,algorithmic}

\newcommand{\e}{\varepsilon}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\question}[1]{\vspace{10pt}\noindent $\mathbf{#1}$}
\newcommand{\yieldstar}{\stackrel{*}{\Rightarrow}}
\newcommand{\yields}{\Rightarrow}
\newcommand{\blank}{\text{\textvisiblespace}}

\newtheorem{objective}{Objective}

\begin{document}
  
  \begin{minipage}{\textwidth}
    CSE3502 - Theory of Computation \hfill \today\\
    \textbf{Due: Before class on April 8, 2014}\\
    \\
    \centering{Homework 6} \hfill
  \end{minipage}

  \input{hw_survey}
  
  \section{Turing Machines} % (fold)
  
    Consider the following Turing machine.
    It uses the convention that if there is no arrow drawn from a particular state for a particular symbol then it transitions to the reject state $q_{11}$ and moves left.
    \[
      \begin{tikzpicture}[scale=0.2]
      \tikzstyle{every node}+=[inner sep=0pt]
      \draw [black] (14.6,-26) circle (3);
      \draw (14.6,-26) node {$q_1$};
      \draw [black] (21.9,-13.4) circle (3);
      \draw (21.9,-13.4) node {$q_2$};
      \draw [black] (42.7,-8.9) circle (3);
      \draw (42.7,-8.9) node {$q_3$};
      \draw [black] (51.8,-17) circle (3);
      \draw (51.8,-17) node {$q_4$};
      \draw [black] (61.4,-29.6) circle (3);
      \draw (61.4,-29.6) node {$q_5$};
      \draw [black] (47.5,-34.9) circle (3);
      \draw (47.5,-34.9) node {$q_6$};
      \draw [black] (50.4,-50.5) circle (3);
      \draw (50.4,-50.5) node {$q_7$};
      \draw [black] (63.5,-43.3) circle (3);
      \draw (63.5,-43.3) node {$q_8$};
      \draw [black] (23.9,-40) circle (3);
      \draw (23.9,-40) node {$q_9$};
      \draw [black] (35.1,-26) circle (3);
      \draw (35.1,-26) node {$q_{10}$};
      \draw [black] (35.1,-26) circle (2.4);
      \draw [black] (8.5,-21.1) -- (12.26,-24.12);
      \fill [black] (12.26,-24.12) -- (11.95,-23.23) -- (11.32,-24.01);
      \draw [black] (15.191,-23.062) arc (163.93622:135.89077:18.335);
      \fill [black] (19.65,-15.37) -- (18.73,-15.6) -- (19.45,-16.3);
      \draw (16.29,-17.71) node [left] {$\substack{0\to \blank,R \\ 1\to \blank,R}$};
      \draw [black] (24.222,-11.504) arc (125.04404:79.37113:20.537);
      \fill [black] (39.8,-8.13) -- (39.11,-7.49) -- (38.92,-8.48);
      \draw (30.75,-7.62) node [above] {$\substack{2\to R\\3\to R}$};
      \draw [black] (45.555,-9.793) arc (65.20927:31.44554:11.587);
      \fill [black] (50.58,-14.27) -- (50.59,-13.32) -- (49.74,-13.85);
      \draw (50.91,-11.17) node [above] {$\substack{\blank\to L}$};
      \draw [black] (54.053,-18.979) arc (46.07661:28.53129:32.656);
      \fill [black] (60.09,-26.9) -- (60.15,-25.96) -- (59.27,-26.44);
      \draw (57.95,-21.31) node [right] {$\substack{1\to \blank,L}$};
      \draw [black] (59.208,-31.642) arc (-52.34906:-85.90774:16.151);
      \fill [black] (50.49,-34.96) -- (51.33,-35.41) -- (51.26,-34.41);
      \draw (56.51,-34.48) node [below] {$\substack{\blank\to R}$};
      \draw [black] (48.565,-37.704) arc (18.4297:2.63216:36.257);
      \fill [black] (50.39,-47.5) -- (50.85,-46.68) -- (49.85,-46.72);
      \draw (50.54,-42.26) node [right] {$\substack{x\to \blank,R}$};
      \draw [black] (62.265,-46.023) arc (-32.52253:-89.88947:10.584);
      \fill [black] (62.26,-46.02) -- (61.41,-46.43) -- (62.26,-46.97);
      \draw (59.93,-50.11) node [below] {$\substack{\blank\to L}$};
      \draw [black] (62.283,-32.466) arc (14.82424:2.60522:37.237);
      \fill [black] (62.28,-32.47) -- (62,-33.37) -- (62.97,-33.11);
      \draw (63.79,-36.16) node [right] {$\substack{1\to \blank,L\\2\to \blank,L}$};
      \draw [black] (21.266,-38.574) arc (-124.10118:-168.70778:15.173);
      \fill [black] (21.27,-38.57) -- (20.88,-37.71) -- (20.32,-38.54);
      \draw (16.52,-35.74) node [left] {$\substack{\blank\to L\\ 2\to R\\ 3\to R}$};
      \draw [black] (25.77,-37.66) -- (33.23,-28.34);
      \fill [black] (33.23,-28.34) -- (32.34,-28.65) -- (33.12,-29.28);
      \draw (30.06,-34.42) node [right] {$\substack{\blank\to L}$};
      \draw [black] (24.07,-15.47) -- (32.93,-23.93);
      \fill [black] (32.93,-23.93) -- (32.7,-23.01) -- (32.01,-23.74);
      \draw (27.04,-20.18) node [below] {$\substack{\blank\to L}$};
      \draw [black] (49.16,-18.42) -- (37.74,-24.58);
      \fill [black] (37.74,-24.58) -- (38.68,-24.64) -- (38.21,-23.76);
      \draw (42.01,-21) node [above] {$\substack{\blank\to L\\ x\to L}$};
      \draw [black] (37.877,-27.13) arc (64.60142:44.0614:26.454);
      \fill [black] (37.88,-27.13) -- (38.39,-27.93) -- (38.81,-27.02);
      \draw (43.4,-29.04) node [above] {$\substack{\blank\to L}$};
      \draw [black] (24.605,-42.904) arc (41.37602:-246.62398:2.25);
      \draw (21.46,-47.21) node [below] {$\substack{2\to R\\3\to R}$};
      \fill [black] (22.02,-42.33) -- (21.09,-42.48) -- (21.75,-43.23);
      \draw [black] (18.927,-13.101) arc (291.99462:3.99462:2.25);
      \draw (15.55,-8.53) node [left] {$\substack{0\to x,R\\1\to x,R}$};
      \fill [black] (20.33,-10.86) -- (20.49,-9.93) -- (19.57,-10.3);
      \draw [black] (43.355,-5.984) arc (195.06881:-92.93119:2.25);
      \draw (48.45,-3.15) node [above] {$\substack{1\to R\\2\to R\\3\to R}$};
      \fill [black] (45.41,-7.65) -- (46.32,-7.92) -- (46.06,-6.96);
      \draw [black] (53.532,-14.565) arc (172.30076:-115.69924:2.25);
      \draw (58.42,-12.63) node [right] {$\substack{2\to \blank,L\\3\to \blank,L}$};
      \fill [black] (54.79,-16.89) -- (55.51,-17.5) -- (55.65,-16.51);
      \draw [black] (47.921,-52.168) arc (-28.33608:-316.33608:2.25);
      \draw (43.03,-51.55) node [left] {$\substack{x\to R\\1\to R\\2\to R}$};
      \fill [black] (47.57,-49.55) -- (47.1,-48.73) -- (46.63,-49.61);
      \draw [black] (63.342,-27.329) arc (167.19859:-120.80141:2.25);
      \draw (68.34,-25.99) node [right] {$\substack{1\to L\\2\to L\\x\to L}$};
      \fill [black] (64.38,-29.76) -- (65.05,-30.42) -- (65.27,-29.45);
      \end{tikzpicture}
    \]
    
    Give the sequence configurations this machine enters from start to halt given the following inputs.
    \begin{itemize}
      \item $1$
      \item $2313$
      \item $222$
      \item $\e$
    \end{itemize}
  
  % section turing_machine_variants (end)

  \section{Multitape Turing Machines} % (fold)
  
    For the next two questions, you may augment the definition of a multitape TM given in class so that the transition function is of the form
    \[                                                                              
      \delta: Q \times \Gamma^k \to Q \times \Gamma^k \times \{L,R,S\}^k,
    \]
    where $S$ indicates that the tape head should stay in the same place rather than move left or right.
    This is often very convenient with multitape TMs.
    This is the definition used in the second and third edition of the book.
    For both, you may assume that the input language is $\Sigma = \{0,1\}$.

    \question{2.1}
      In class, we saw how to use a multitape Turing machine to simulate a nondeterministic Turing machine.
      One important step in that simulation was to copy the input from the first tape to the second.
      For this question give a description of a $2$-tape Turing machine $C = \{Q_c,\Sigma, \Gamma,\delta_c, q_c, c_{accept}, c_{reject})$ that copies the input string from tape 1 to tape 2.
      When done, it should return both heads to the beginning of the tapes and accept.
      Describe the transition function using a state diagram.
  
    \question{2.2}
      Let $M_1 = (Q_1, \Sigma, \Gamma, \delta_1, q_1, \text{accept}_1, \text{reject}_1)$ and $M_2 = (Q_2, \Sigma, \Gamma, \delta_2, q_2, \text{accept}_2, \text{reject}_2)$ be one-tape Turing machines.
      Describe a $2$-tape Turing machine that accepts the language $L(M_1)\cup L(M_2)$.
      Give a formal description that includes the full $7$-tuple.
      Describe the transition function directly from the transition functions $\delta_1$ and $\delta_2$.
  
  % section multitape_turing_machines (end)

  \section{Turing-Recognizable vs. Turing-Decidable} % (fold)
  
    \question{3.1}
      Suppose $A$ is a Turing-recognizable language such that $A = B \cup C$ where $B$ is Turing-decidable and $\overline{C}$ is Turing-recognizable.
      Prove that $A$ is Turing-decidable.
    
  % section turing_recognizable_vs_turing_decidable (end)

\end{document}