%
% Assignment 3b for CS3530 Computational Theory:
% Turing Machines
% Fall 2024
%
% Problems taken from Sipser
%

\documentclass{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ae,aecompl}
\usepackage{enumerate}

% skip for paragraphs, don't indent
\parskip 6pt plus 1pt
\parindent=0pt
\raggedbottom

% a list environment with no bullets or numbers
\newenvironment{indentlist}{\begin{list}{}{\addtolength{\itemsep}{0.5\baselineskip}}}{\end{list}}

\begin{document}
\begin{center}
\textbf{\Large CS 3530: Assignment 3b} \\[2mm]
Fall 2024
\end{center}

\raggedright

\section*{Exercise 3.5ab (5 points)}

\subsection*{Problem}

Examine the formal definition of a Turing machine to answer the following questions,
and explain your reasoning.

Note: Refer to the definition 3.3 in the textbook.

\begin{itemize}
\item [a.] Can a Turing machine ever write the blank symbol $\sqcup$ on its tape?
\item [b.] Can the tape alphabet $\Gamma$ be the same as the input alphabet $\Sigma$?
\end{itemize}

\subsection*{Solution}

\begin{itemize}
\item [a.] 
\item [b.] 
\end{itemize}

\section*{Exercise 3.7 (5 points)}

\subsection*{Problem}

Explain why the following is not a description of a legitimate Turing machine.

Let $M_\text{bad} = $ ``The input is a polynomial $p$ over variables $x_1, \cdots, x_k$.
\begin{enumerate}
\item Try all possible settings of $x_1, \cdots, x_k$ to integer values.
\item Evaluate $p$ on all of these settings.
\item If any of these settings evaluates to $0$, \emph{accept};  otherwise, \emph{reject}.''
\end{enumerate}

Note: Look at the subsection \emph{Hilbert's Problems} for more information on polynomials
and finding integral roots.

\subsection*{Solution}


\section*{Exercise 3.15ab (10 points)}

\subsection*{Problem}

Show that the collection of decidable languages is closed under the operation of

\begin{itemize}
\item [a.] union.
\item [b.] concatenation.
\end{itemize}

\subsection*{Solution}

\begin{itemize}
\item [a.] 
\item [b.] 
\end{itemize}


\end{document}
