% Created 2023-11-02 Thu 12:14
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\notindent \notag  \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
\author{Elizabeth Hunt (A02364151)}
\date{\today}
\title{HW 06}
\hypersetup{
 pdfauthor={Elizabeth Hunt (A02364151)},
 pdftitle={HW 06},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 28.2 (Org mode 9.7-pre)}, 
 pdflang={English}}
\begin{document}

\maketitle
\setlength\parindent{20pt}

\section{Problem One}
\label{sec:orgf4c2128}
\subsection{1 - \{ a\textsuperscript{i} b\textsuperscript{j} c\textsuperscript{k} | i > j > k \}}
\label{sec:orgd221679}
We assume that there exists a Context Free Language, \(L\) such that \(L = { a^i b^j c^k | i > j > k }\).
Then by the Pumping Lemma for Context Free Languages, for each \(z \in L\) of sufficient length \(n\) we can
split \(z\) into the sequence of substrings \(uvwxy\) with \(|vx| \geq 1\) and \(|vwx| \le n\). Any such "pumped"
string \(uv^i w x^i y \forall i \ge 0\) is also in \(L\).

Consider the string \(a^{n+2} b^{n+1} c^{}^n \in L\) which is always longer than \(n\) (the integer of the Pumping Lemma)
so it is of sufficient length. Splitting this up according to the aforementioned Lemma, we know
\(|vwx| \le n\) and thus the string \(vx\) contains either all of one letter or two different letters.

If \(vx\) contains only \(a\)'s or \(b\)'s then we can "pump" \(vx\) 0 times to produce \(z^* = u v^0 w x^0 y\) and
since \(|vx| \geq 1\) then we lose \(p \geq 1\) \(a\)'s or \(b\)'s. Thus, in the case of \(a\), \((n+2)-p \leq n+1\) and
\(z^*\) is not in \(L\), and in the case of \(b\), \((n+1)-p \leq n\), with the same conclusion.

If \(vx\) contains only \(c\)'s then we can "pump" \(vx\) \(n\) times to produce \(z^* = u v^n w x^n y\) at least
\(2n\) the number of \(c's\) (which is always \(\ge n\)), and there would be equal or more \(c\)'s to
\(b\)'s and thus \(z^* \notin L\).

If \(vx\) contains both \(a\)'s and \(b\)'s then we can "pump" \(vx\) 0 times similar to the case of only \(a\)'s
and \(b\)'s to produce a string with an equal or less number of \(b\)'s than \(c\)'s.

If \(vx\) contains both \(b\)'s and \(c\)'s then we can "pump" \(vx\) \(3n\) times to come up with a string that
will always have \(b\)'s and \(c\)'s greater or eqaul to the number of \(a\)'s.

\subsection{2 - \{ a\textsuperscript{i} b\textsuperscript{j} | i = j\textsuperscript{2} \}}
\label{sec:org5f8cc3e}

We assume that there exists a Context Free Language, \(L\) such that \(L = { a^i b^j | i = j^2 }\).

Then by the Pumping Lemma for Context Free Languages, for each \(z \in L\) of sufficient length \(n\) we can
split \(z\) into the sequence of substrings \(uvwxy\) with \(|vx| \geq 1\) and \(|vwx| \le n\). Any such "pumped"
string \(uv^i w x^i y \forall i \ge 0\) is also in \(L\).

Consider the string \(a^{n^2}^{} b^{}^n \in L\) which is always longer than \(n\) (the integer of the Pumping Lemma)
so it is of sufficient length. Splitting this up according to the aforementioned Lemma, we know
\(|vwx| \le n\) and thus the string \(vx\) contains either all of one letter or two different letters.

\begin{enumerate}
\item If \(vx\) contains only \(a\)'s then we can "pump" \(vx\) 0 times to produce \(z^* = u v^0 w x^0 y\) and
since \(|vx| \geq 1\) then we lose \(p \geq 1\) \(a\)'s and thus \(z^* = a^{n^2 - p} b^n \notin L\) as \(n^2 - p \ne n^2\).

\item If \(vx\) contains only \(b\)'s then we can "pump" \(vx\) 2 times to produce \(z^* = u v^2 w x^2 y\) and
since \(|vx| \geq 1\) then we add \(p \geq 2\) \(b\)'s and thus \(z^* = a^{n^2} b^{n+p} \notin L\) as \(n^2 \ne (n + p)^2\).

\item If \(vx\) contains both \(b\)'s and \(a\)'s then we can prove that we can construct a number of times to pump
such that the relationship for \(i = j^2\) cannot be satisfied:
\begin{itemize}
\item \(v\) must contain only \(a\)'s and \(x\) must contain only \(b\)'s; else we could pump and obtain a string
in which the order of \(a\)'s and \(b\)'s is disrupted.
\item Let \(y = |v|\) and \(u = |x|\) with \(1 \leq y + u \le n\) since \(|vwx| \le n\) and \(|vx| \geq 1\).
Then we can pump \(p \geq 1\) times to create the string
\(z^* = a^{(n^2 - y) + py} b^{(n - u) + pu} = a^{n^2 + p(y-1)} b^{n + p(u-1)}\).
\item Then for any such \(n, u, y\) we can find a \(p\) such that
\((n + p(u - 1))(n + p(u - 1)) = n^2 + 2pn(u-1) + p^2(u-1)^2 \neq n^2 + p(y-1)\)
since \(u\) and \(y\) are positive.
\end{itemize}
\end{enumerate}

\subsection{3 - \{ a\textsuperscript{i} | i is prime \}}
\label{sec:orgc7ac705}

We assume that there exists a Context Free Language, \(L\) such that \(L = { a^i b^j | i = j^2 }\).

Then by the Pumping Lemma for Context Free Languages, for each \(z \in L\) of sufficient length \(n\) we can
split \(z\) into the sequence of substrings \(uvwxy\) with \(|vx| \geq 1\) and \(|vwx| \le n\). Any such "pumped"
string \(uv^i w x^i y \forall i \ge 0\) is also in \(L\).

Consider the string \(z = a^{p(n)} \in L\) where \(p(n)\) is a function returning the first prime number greater
than \(n\); this string is always longer than \(n\) (the integer of the Pumping Lemma) so
it is of sufficient length. Splitting this up according to the aforementioned Lemma, we know
\(|vwx| \le n\) and thus the string \(vx\) is made up of one or more \(a\)'s.

Given \(t = |v|\) and \(u = |x|\), and \(1 \le t + u \le n\); we can simply pump \(vx\) \(p(n)\) times to obtain
the string \(z^* = uv^{tp(n)} w x^{up(n)}y\) which is \(a^{p(n) + tp(n) + up(n)}\). And \(p(n) + tp(n) + up(n)\) is not prime
since it can be factored into \(p(n)(1 + t + u)\); as either \(t\) or \(u\) is greater than one, then
\(z^* \notin L\).

\section{Problem Two}
\label{sec:org0e7b7e5}

\url{https://bit.ly/cs5000-simponic-hw06-p02}


\section{Problem Three}
\label{sec:org3b85eb1}

\url{https://bit.ly/cs5000-simponic-hw06-p03}

In english(ish):

\begin{enumerate}
\item If the current symbol is \(B\), move right and goto 2

\item If the current symbol is \(a, b, c\), move right and goto 2. If the current symbol is \(B\), move Left and goto 3.
If the current symbol is * we move left and goto 6.

\item We're at the last \(c\) in the string. If the current symbol is \(c\) then we print \$ and go left until
we see an \(a\). Then, move Left and go to 4.

\item If the current symbol is \(b\) then we print * and go right until we see \$. At which we move left and
goto 3. If the symbol is * then we move right and goto 5.

\item If the current symbol is b, c, *, we move right and goto 5. If it's \$ we move left and goto 2 to do the next
iteration.

\item We move left until we hit \(B\) at which we move right and goto 7.

\item We're now at the beginning of the \(a\)'s after replacing all \(c\)'s with \$ and \(b\)'s with *. If we read
an \(a\) we print \(+\) and goto 8. If we see a \(-\) (which we replace \(*\)'s with), we accept.

\item If the current symbol is \(+, a, *\), we move right and goto 8. If we see \$ or \(-\) we move left and
goto 9.

\item If the current symbol is \(*\) then we print \(-\) and goto 9. If we see \(-\) we move left and goto 10.

\item If the current symbol is \(*, a\) then we move left and goto 10. If we see \(+\) we move right and goto
7 to do another iteration.
\end{enumerate}


\section{Problem Four}
\label{sec:orgdacb3cd}
We can write the control tuples for the two-tape turing machine in the form: \((q_{\text{from}} , s_1, s_2, a_1, a_2, q_{\text{to}})\) 
where s\textsubscript{n} is the expected symbol on tape \(n\), \(a_n\) is the action (R / L / new symbol) to perform on tape \(n\), \(q_{\text{from}}\)
is the current state, and \(q_{\text{to}}\) is the next state.

At a high level we can translate these control tuples to a single tape by separating the single tape into two sections; the
first section simulates the first tape, and the other the second tape. These can be split by a single symbol \texttt{+} not in the alphabet (with the
first cell also being \texttt{+}, representing the beginning of the input on the first tape). Additionally, the position of the tape
head of the turing machine being simulated in its section can be delimited by some symbol not in the input alphabet in each section; call this
symbol \texttt{*}.

Thus, to build the initial tape we can construct the tape \texttt{+ * <input on tape 1> + * <input on tape 2>} (the head being at the beginning).
Then, for each tuple in the two-tape turing machine \((q_{\text{from}} , s_1, s_2, a_1, a_2, q_{\text{to}})\) we construct a set of new states that will:

\begin{enumerate}
\item Search until we find \texttt{*} (we're at the head of the first "tape"), at which we go right one, and if we read s\textsubscript{1} goto 2.
\item Search until we find \texttt{*} (we're at the head of the second "tape"), at which we go right one, and if we read s\textsubscript{2} goto 3.
\item We perform a\textsubscript{2}.
\begin{itemize}
\item If \(s_2\) is the \texttt{+} symbol, we perform a new set of states to analyze the next symbol after; if it's non-\texttt{+} we shift all symbols proceeding
to the right (this is a catch for 4 in the case we need to overwrite the \texttt{+} cell delimiting the two sections) and print a blank symbol. Then continue.
\item If a\textsubscript{2} is "R" then we go left one (to the \texttt{*}), write s\textsubscript{2}, and go right one.
\item If a\textsubscript{2} is "L" then we go back 2 (to the symbol preceding \texttt{*}) and from a new set of states constructed from all symbols in the alphabet go right and copy that symbol.
Then we go back one and print "*".
\item Else, we print a\textsubscript{2}.
\item Finally, go left and goto 4.
\end{itemize}
\item Move left until we find \texttt{*} (we're now at the head of the first "tape") again and perform the same algorithm as 3 but with \(s_2 \rightarrow s_1 , a_2 \rightarrow a_1\). Then goto 5.
\item Move left until we find the \texttt{+} symbol (we're at the head of the first tape) and move to the state corresponding to 1 with q\textsubscript{\text{to}}.
\end{enumerate}

\section{Problem Five}
\label{sec:orgab00621}
We can write the control quadruples for the 3D turing machine in the form: \((q_{\text{from}}, s, a, q_{\text{to}})\)
where \(s\) is the expected symbol and \(a\) is the movement action \(\{ +x, -x, +y, -y, +z, -z \}\) or a symbol to print;
where each movement action is a single step on the specified axis by either positive or negative one.

At a high level we will apply our strategy in Problem 4 of delimination to construct several rows of tape into a
"matrix" and then scale those into several matrices to produce a 3-dimensional tape; as one could emulate with
\texttt{(make-array (list z y x))}.

Then if we construct a one dimensional tape such that each "row" is a "tape" in the z axis then we "paste" the input
into a one dimensional tape in the form \texttt{- = + * \_ <...[(0, 0, 0), (0, 0, 1)...]>} with the first five unique symbols not in the alphabet;
the \texttt{-} indicating a new "matrix" in the z-y plane, and each \texttt{+} symbol a new row in the z direction. But now, we need to keep track of
where we are in the \(z\) and \(y\) planes for every \(x\). To do so we can also create another three new symbols not in the
alphabet; say \texttt{*} to stick with Problem 4 for the \(z\) plane, \texttt{=} for the \(y\) plane, and \texttt{\_} for the actual placement of the
current head of the machine.

Now, for each control tuple of the 3D turing machine we can construct a new set of states that will, at a high level:

\begin{enumerate}
\item Search until we find \texttt{\_} (we're at the head of the tape), at which we go right one, and if we read \(s\) goto 2.
\item If \(a\) is \(\pm z\) then we move right or left.
\begin{itemize}
\item If this symbol is \texttt{+} we must then traverse to the very beginning of the tape and "increase the size" of every single \(z\) since the
tape has the potential to now go in the \(x\) or \(y\) axes; we do this by searching for the first \texttt{+}, move right, shift the entire tape
right one and print a blank symbol (to add an extra cell at the beginning), then continue searching for \texttt{+} and for each: shift the entire tape right one,
move left, print a blank symbol, move right two, shift everything to the right one, move left, and print a blank symbol (adding a blank cell before and after
each \texttt{+}).
\item Then we go back to the beginning of the tape and continue moving right until we see \texttt{\_}.
\end{itemize}
\item If \(a\) is \(\pm y\) or \(\pm x\) then move left or right until the first instance of either \texttt{=} or \texttt{-} respectively and perform a similar kind of algorithm to copy
the rows or matrices with blank \(z\) rows of the same size, adding rows / matrices if necessary should we hit the beginning or end of the tape (for \(x\)) or
a new "matrix" (\texttt{-} for \(y\))..
\end{enumerate}
\end{document}