\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,graphicx, pgf, tikz}
\usetikzlibrary{arrows,automata}
\setlength{\textwidth}{7in}
\setlength{\topmargin}{-0.575in}
\setlength{\textheight}{9.25in}
\setlength{\oddsidemargin}{-.25in}
\setlength{\evensidemargin}{-.25in}
\reversemarginpar
\setlength{\marginparsep}{-15mm}
\newcommand{\rmv}[1]{}
\newcommand{\bemph}[1]{{\bfseries\itshape#1}}
\newcommand{\N}{\mathbb{N}} %natural numbers
\newcommand{\Z}{\mathbb{Z}} %integers
\newcommand{\R}{\mathbb{R}} % reals
% Shortcuts for describing Turing machines
\newcommand{\qa}{\ensuremath{q_{a}}} %accepting state is \qa
\newcommand{\qr}{\ensuremath{q_{r}}} %rejecting state is \qr
\newcommand{\blank}{\ensuremath{b\!\!\!/}} % blank symbol is \blank
% Here the user must define certain strings for this homework assignment
%
\def\CourseCode{6902} % e.g. B38
\def\AssignmentNo{1} % e.g. 1
\def\DateHandedOut{May 16, 2018} % e.g. September 18, 2002
\def\DateDue{May 30, 2018} % e.g. October 1, 2002
\def\TimeDue{10pm} % e.g. 11 am
\begin{document}
\noindent
MUN CS \CourseCode \hfill \DateHandedOut\\
\begin{center}
Homework Assignment \#\AssignmentNo\\
Due: \DateDue\ at \TimeDue\\
Please typeset the assignment in LaTeX, and upload the pdf file on Brightspace (D2L, online.mun.ca). \\
\medskip
%%%%%% M A K E S U R E T O W R I T E Y O U R N A M E H E R E!!! %%%%%%%%%%%%%%%
\textbf{YOUR NAME HERE} \\
\end{center}
\begin{enumerate}
\item \textbf{Asymptotic notation} \marginpar{[10]} \\
Let $f, g$ be functions on natural numbers. Recall the definitions of $f(n) \in O(g(n))$ ($\exists n_0, c >0 \forall n > n_0 f(n) \leq c\cdot g(n))$ and a symmetric definition of $\Omega(g(n))$ (same except $f(n) \geq c\cdot g(n))$. We say $f(n) \in \Theta(g(n))$ if both $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n)$.) Consider the following 12 functions (here, all logs are base two): $3n^2$, $n\cdot \log^3 n$, $n\cdot \log n$, $2^{n/3}$, $2^n$, $n^2 - \log n$, $\log{(n^{3n})}$, $2^{n^{0.2}}$, $ \sqrt{n^4}$, $n \cdot \log (n^3)$, $\frac{1}{100} 2^n$, $\log{(2^{10 n\cdot n})} $.
\begin{enumerate}
\item List all groups of functions above that have the same asymptotic complexity (that is, they are in $\Theta$ of each other).
{\em Solution:
}
\item Arrange these functions in the order of increasing asymptotic complexity (that is, functions earlier in your sequence should be $\in O()$ of later functions).
{\em Solution:
}
\end{enumerate}
\item \textbf{Finite automata and Turing machines} \marginpar{[25]}
We talked in class about encoding all kinds of possible inputs (graphs, Turing machines, sequences of numbers) as binary strings. In this problem, you will play with one possible encoding of pairs of binary strings. This is not the most efficient encoding, but it is simple to describe. The idea is to use even tape cell positions to hold the strings themselves, with odd cell positions indicating whether we are on a number or on a "delimiter". You can also think about it as treating each pair of cells as a symbol, with "00" and "01" corresponding to "0" and "1", respectively, and say "11" corresponding to a delimiter. More specifically, suppose the input is a pair of strings $x = x_1 \dots x_n$ and $y = y_1 \dots y_m$ over ${0,1}$ (for example, $x=010$ and $y=01$). Then the pair $\langle x, y \rangle$ will be represented as $ 0 x_1 0 x_2 0 ... 0 x_n 1 1 0 y_1 0 y_2 0 \dots 0 y_m$. For example, $\langle 010, 01\rangle$ will be encoded as 000100110001.
\begin{enumerate}
\item Give a deterministic finite automaton accepting a set of valid pairs of binary strings in the above encoding. Note that strings can be empty.
{\em Solution:
%% The best way to draw an automaton in LaTeX is using TikZ library. See below for an example from the manual.
%% Here is TikZ manual: http://www.texample.net/media/pgf/builds/pgfmanualCVS2012-11-04.pdf
%% You can also use a tool at http://madebyevan.com/fsm/ which would generate TikZ code for you.
%% Alternatively, you can draw the automaton using some other tool, and insert it with \includegraphics{yourfile} command.
%\begin{tikzpicture}[shorten >=1pt,node distance=2cm,auto]
%
% \node[state,initial] (q_0) {$q_0$};
% \node[state] (q_1) [above right of=q_0] {$q_1$};
% \node[state] (q_2) [below right of=q_0] {$q_2$};
% \node[state,accepting] (q_3) [below right of=q_1] {$q_3$};
%
% \path[->] (q_0) edge node {0} (q_1)
% edge node [swap] {1} (q_2)
% (q_1) edge node {1} (q_3)
% edge [loop above] node {0} ()
% (q_2) edge node [swap] {0} (q_3)
% edge [loop below] node {1} ();
%\end{tikzpicture}
}
\item Give a full description of a Turing machine which takes a pair of binary strings encoded as above, and accepts if and only if the two strings are equal. (First give a high-level description of how your Turing machine works, then give a formal description specifying $\Sigma, \Gamma, Q$ with $q_0, \qa,\qr$ and a table for $\delta$).
{\em Solution:
%% you can use shortcuts (defined at the start of the file): \qa for q_{accept}, \qr for q_{reject}, \blank for the blank symbol.
%% Here is a table for $\delta$ from the example in the notes
%
%\begin{tabular}{|c|c|c|} \hline
%\em State $q$ & \em Symbol $s$ & \em Action $\delta(q,s)$ \\ \hline
%$q_0$ & 0 & $(q_0,\blank,R)$ \\
%$q_0$ & 1 & $(q_1,\blank,R)$ \\
%$q_0$ & \blank & $(\qa,\blank,L)$ \\\hline
%$q_1$ & 0 & $(q_1,\blank,R)$ \\
%$q_1$ & 1 & $(q_0,\blank,R)$ \\
%$q_1$ & \blank & $(\qr,\blank,L)$ \\\hline
%\end{tabular}
}
\item Give a description of a multi-tape Turing machine which starts with two numbers (possibly with leading 0s) encoded as a pair of binary strings as above, and outputs a single number (without any extra encodings) which is equal to the sum of the two input numbers. If the input is not valid, finish in $q_r$; otherwise finish in $q_a$ pointing to the first symbol of the output with nothing other than the answer on the first tape (for this problem, ignore that there might be something on the other tape(s) when your TM stops).
{\em Solution:
}
\end{enumerate}
\item \textbf{Computability of languages}. \marginpar{[35]}\\ For each of the
following languages determine whether the language is decidable,
semi-decidable, co-semi-decidable, or is higher in the arithmetic
hierarchy. For the easiness proofs, give algorithms; for the
hardness proofs, give reductions (ideally, from $A_{TM}$. ) For each
problem, start by writing the language descriptions using
quantifiers.
\begin{enumerate}
\item $A_{Composite} = \{ \mid$ the language of $M$ contains
only composite (non-prime) numbers $\geq 2\}$.
{\em Solution:
}
\item $INF = \{ \mid$ the language of $M$ is an infinite set $\}$.
{\em Solution:
}
\item $Halt_{110} = \{ \mid M$ halts on \emph{some string}
containing a substring 110$\}$.
{\em Solution:
}
\item $A_{10Gb} = \{ \mid M$ halts running on a mobile device with 10Gb
of memory \}
{\em Solution:
}
\end{enumerate}
\item \textbf{Closure of the class of semi-decidable languages under Kleene star.} \marginpar{[10]}\\
Suppose that $L$ is semi-decidable. Define a closure $L^*$ of $L$ as \(L^*=
\{ x_1\dots x_k \mid k \in \mathbb{N}, \forall i, 1 \leq i \leq k, \
x_i \in L \} \) (that is, strings in $L^*$ are finite sequences of
strings from $L$). Show that $L^*$ is also semi-decidable using the definition of semi-decidable in terms of
existence of a verifier.
{\em Solution:
}
\end{enumerate}
\end{document}