InitHEADmain

3 files changed, 394 insertions, 0 deletions

diff --git a/Homework/cs5000/hw06/hw06.org b/Homework/cs5000/hw06/hw06.org
new file mode 100644
index 0000000..c48e3f5
--- /dev/null
+++ b/Homework/cs5000/hw06/hw06.org
@@ -0,0 +1,174 @@
+#+TITLE: HW 06
+#+AUTHOR: Elizabeth Hunt (A02364151)
+#+STARTUP: entitiespretty fold inlineimages
+#+LATEX_HEADER: \notindent \notag  \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
+#+LATEX: \setlength\parindent{20pt}
+#+OPTIONS: toc:nil
+
+* Problem One
+** 1 - { a^i b^j c^k | i > j > k }
+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.
+
+** 2 - { a^i b^j | i = j^2 }
+
+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.
+
+1. 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$.
+
+2. 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$.
+
+3. 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:
+   + $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.
+   + 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)}$.
+   + 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.
+
+** 3 - { a^i | i is prime }
+
+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$.
+
+* Problem Two
+
+[[https://bit.ly/cs5000-simponic-hw06-p02]]
+
+
+* Problem Three
+
+[[https://bit.ly/cs5000-simponic-hw06-p03]]
+
+In english(ish):
+
+1. If the current symbol is $B$, move right and goto 2
+   
+2. 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.
+   
+3. 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.
+
+4. 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.
+
+5. 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.
+
+6. We move left until we hit $B$ at which we move right and goto 7.
+
+7. 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.
+
+8. If the current symbol is $+, a, *$, we move right and goto 8. If we see $ or $-$ we move left and
+   goto 9.
+
+9. If the current symbol is $*$ then we print $-$ and goto 9. If we see $-$ we move left and goto 10.
+
+10. 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.
+
+
+* Problem Four
+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_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 ~+~ not in the alphabet (with the
+first cell also being ~+~, 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 ~*~.
+
+Thus, to build the initial tape we can construct the tape ~+ * <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:
+
+1. Search until we find ~*~ (we're at the head of the first "tape"), at which we go right one, and if we read s_1 goto 2.
+2. Search until we find ~*~ (we're at the head of the second "tape"), at which we go right one, and if we read s_2 goto 3.
+3. We perform a_2.
+   + If $s_2$ is the ~+~ symbol, we perform a new set of states to analyze the next symbol after; if it's non-~+~ we shift all symbols proceeding
+     to the right (this is a catch for 4 in the case we need to overwrite the ~+~ cell delimiting the two sections) and print a blank symbol. Then continue.
+   + If a_2 is "R" then we go left one (to the ~*~), write s_2, and go right one.     
+   + If a_2 is "L" then we go back 2 (to the symbol preceding ~*~) 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 "*".
+   + Else, we print a_2.
+   + Finally, go left and goto 4.
+4. Move left until we find ~*~ (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.
+5. Move left until we find the ~+~ symbol (we're at the head of the first tape) and move to the state corresponding to 1 with q_{\text{to}}.
+
+* Problem Five
+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
+~(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 ~- = + * _ <...[(0, 0, 0), (0, 0, 1)...]>~ with the first five unique symbols not in the alphabet;
+the ~-~ indicating a new "matrix" in the z-y plane, and each ~+~ 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 ~*~ to stick with Problem 4 for the $z$ plane, ~=~ for the $y$ plane, and ~_~ 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:
+
+1. Search until we find ~_~ (we're at the head of the tape), at which we go right one, and if we read $s$ goto 2.
+2. If $a$ is $\pm z$ then we move right or left.
+   + If this symbol is ~+~ 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 ~+~, 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 ~+~ 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 ~+~).
+   + Then we go back to the beginning of the tape and continue moving right until we see ~_~.
+3. If $a$ is $\pm y$ or $\pm x$ then move left or right until the first instance of either ~=~ or ~-~ 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" (~-~ for $y$)..
diff --git a/Homework/cs5000/hw06/hw06.pdf b/Homework/cs5000/hw06/hw06.pdf
new file mode 100644
index 0000000..d898ce4
--- /dev/null
+++ b/Homework/cs5000/hw06/hw06.pdf
diff --git a/Homework/cs5000/hw06/hw06.tex b/Homework/cs5000/hw06/hw06.tex
new file mode 100644
index 0000000..3d0af5f
--- /dev/null
+++ b/Homework/cs5000/hw06/hw06.tex
@@ -0,0 +1,220 @@
+% 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}
\ No newline at end of file