InitHEADmain

1 files changed, 265 insertions, 0 deletions

diff --git a/Homework/cs5000/midterm02/midterm.tex b/Homework/cs5000/midterm02/midterm.tex
new file mode 100644
index 0000000..6848ed7
--- /dev/null
+++ b/Homework/cs5000/midterm02/midterm.tex
@@ -0,0 +1,265 @@
+% Created 2023-11-17 Fri 13:57
+% 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 08}
+\hypersetup{
+ pdfauthor={Elizabeth Hunt (A02364151)},
+ pdftitle={HW 08},
+ pdfkeywords={},
+ pdfsubject={},
+ pdfcreator={Emacs 28.2 (Org mode 9.7-pre)}, 
+ pdflang={English}}
+\begin{document}
+
+\maketitle
+\tableofcontents
+
+\setlength\parindent{0pt}
+
+\section{Problem One}
+\label{sec:orgbeb25aa}
+\begin{center}
+\includegraphics[width=7cm]{./p1.png}
+\end{center}
+
+\section{Problem Two}
+\label{sec:orgc078de2}
+\begin{center}
+\includegraphics[width=7cm]{./p2.png}
+\end{center}
+
+\section{Problem Three}
+\label{sec:orga508990}
+Using the following code proceeding the appendix we receive
+
+\(l(111) = 4\)
+
+\(r(111) = 3\)
+
+\(lt(111) = 12\)
+
+\begin{verbatim}
+const p3 = () => {
+  const x = 111;
+  const { l, r } = lr(x);
+  const lt = length(x);
+
+  [`l(${x}) = ${l}`, `r(${x}) = ${r}`, `lt(${x}) = ${lt}`].forEach((s) =>
+    console.log(s)
+  );
+};
+p3();
+\end{verbatim}
+
+\section{Problem Four}
+\label{sec:org7ca236e}
+Using the following code proceeding the appendix we receive
+
+\((17)_0 = 0\)
+
+\((17)_1 = 0\)
+
+\((17)_2 = 0\)
+
+\((17)_3 = 0\)
+
+\((17)_4 = 0\)
+
+\((17)_5 = 0\)
+
+\((17)_6 = 0\)
+
+\((17)_7 = 1\)
+
+\((17)_8 = 0\)
+
+\begin{verbatim}
+const p4 = () => {
+  const x = 17;
+
+  for (let i = 0; i <= 8; i++) 
+    console.log(`(${x})_${i} = ${access(x, i)}`)
+};
+p4();
+\end{verbatim}
+
+
+And for all \(i > 8\), \(p_i > 17\) and thus \(p_i^{(t+1)} \nmid x\) for all \(t \ge 0\), and thus the valid set of \(t\)'s,
+\(T\), has \(\text{min}(T) = 0\), so \((17)_i = 0\).
+
+\section{Problem Five}
+\label{sec:org25e3a57}
+We compute the new code:
+
+\([\#(I_1), \#(I_2)]\)
+
+For \(\#(I_1)\):
+
+\(\#(I_1) = \langle a, \langle b, c \rangle \rangle\) where \(a = \#(B1) = 2\), \(b = 1\), \(c = \#(X1) - 1 = 1\), so
+\(\#(I_1) = \langle 2, \langle 1, 1 \rangle \rangle = 2^2(2\langle1, 1\rangle + 1) - 1 = 4(11) - 1 = 43\).
+
+For \(\#(I_2)\):
+
+\(\#(I_2) = \langle a, \langle b, c \rangle \rangle\) where \(a = 0\) as there is no label for the instruction, \(b = \#(B1) + 2 = 4\),
+\(c = \#(X1) - 1 = 1\), so \(\#(I_2) = \langle 0, \langle 4, 1 \rangle \rangle = 2^0(2\langle 4, 1 \rangle + 1) - 1 = 94\).
+
+Thus:
+
+\([43, 94] = (2^{43})(3^{94}) - 1 = 6218530334586699211614548872374762259672175972138197450751\).
+
+\section{Problem Six}
+\label{sec:orgc5e0177}
+\subsection{\(\phi\)\textsubscript{5}\textsuperscript{1}(x)}
+\label{sec:orgf652342}
+\(\phi\)\textsubscript{5}\textsuperscript{1}(x) has source \(5 + 1\) = \(6\) which corresponds to the godel sequence \(2^1 * 3^1 = [1, 1]\). 1 =
+\(\langle 1, \langle 0, 0 \rangle \rangle\) which corresponds to an instruction with \(\#(L) = 1\), \(\#(V) = 0\), and an operation
+of \(0\):
+
+\begin{verbatim}
+[ A1 ] Y <- Y
+[ A1 ] Y <- Y
+\end{verbatim}
+
+\subsection{\(\phi\)\textsubscript{7}\textsuperscript{1}(x)}
+\label{sec:orgd9de496}
+\(\phi\)\textsubscript{7}\textsuperscript{1}(x) has source \(7 + 1\) = \(8\) which corresponds to the godel sequence \(2^3 = [3]\). 3 =
+\(\langle 2, \langle 0, 0 \rangle \rangle\) which corresponds to an instruction with \(\#(L) = 2\), \(\#(V) = 0\), and an
+operation of \(0\):
+
+\begin{verbatim}
+[ B1 ] Y <- Y
+\end{verbatim}
+
+\subsection{\(\phi\)\textsubscript{11}\textsuperscript{1}(x)}
+\label{sec:orge5e7392}
+\(\phi\)\textsubscript{11}\textsuperscript{1}(x) has source \(11 + 1\) = \(12\) which corresponds to the godel sequence \(2^2 * 3^1 = [2, 1]\). 2 =
+\(\langle 0, \langle 1, 0 \rangle \rangle\) which corresponds to an instruction with \(\#(L) = 0\), \(\#(V) = 0\), and an
+operation of \(1\).
+
+And, we already found \(1\) in \(\phi\)\textsubscript{5}\textsuperscript{1}(x):
+
+\begin{verbatim}
+Y <- Y + 1
+[ A1 ] Y <- Y
+\end{verbatim}
+
+\subsection{\(\phi\)\textsubscript{13}\textsuperscript{1}(x)}
+\label{sec:org65f2245}
+\(\phi\)\textsubscript{13}\textsuperscript{1}(x) has source \(13 + 1\) = \(14\) which corresponds to the godel sequence \(2^1 * 7^1 = [1, 0, 0, 1]\).
+And, we already found \(1\) in \(\phi_5^1(x)\), \(0\) is trivially \texttt{Y <- Y} (unlabeled, \(\#(V) = 0\), op = 0).
+
+\begin{verbatim}
+[ A1 ] Y <- Y
+Y <- Y
+Y <- Y
+[ A1 ] Y <- Y
+\end{verbatim}
+
+\subsection{\(\phi\)\textsubscript{17}\textsuperscript{1}(x)}
+\label{sec:orgacbaf8a}
+\(\phi\)\textsubscript{17}(x) has source \(17 + 1\) = \(18\) which corresponds to the godel sequence \(2^1 * 3^2 = [1, 2]\).
+And, we already found \(1\) in \(\phi_5^1(x)\), and \(2\) in \(\phi\)\textsubscript{11}\textsuperscript{1}(x)
+
+\begin{verbatim}
+[ A1 ] Y <- Y
+Y <- Y + 1
+\end{verbatim}
+
+\section{Problem Seven}
+\label{sec:org15f3033}
+\begin{enumerate}
+\item Let \(m(x_1, x_2) = x_1 * x_2\) which is primitive recursive by proofs in class.
+\item Let \(four(x_1) = s(s(s(s(n(x_1)))))\); the successor function composed 4 times on the null function.
+\item Then \(f(x_1)\) is \(m(four(x_1), x_1)\) which is an application of composition of primitive recursive functions.
+\end{enumerate}
+
+Thus, \(f\) is primitive recursive, and thus computable.
+
+\section{Problem Eight}
+\label{sec:org1d07ae0}
+We can use the handy identity that \(lcm(x_1, x_2) = \frac{(a * b)}{gcd(a, b)} = \lfloor \frac{(a * b)}{gcd(a, b)} \rfloor\)
+since \(gcd(a, b)\) by definition divides \(a * b\).
+
+\begin{enumerate}
+\item Define \(gcd(x_1, 0) = x_1\)
+\item Let \(R(x_1, x_2)\) be the remainder function when \(x_1\) divides \(x_2\) which is primitive recursive by
+the proof found on page 56 of the book.
+\item We construct the informal recursion \(gcd(x_1, x_2) = gcd(x_2, R(x_1, x_2))\) by Euclid's Algorithm.
+\item Let \(floordiv(x_1, x_2)\) be the floor of the result of division \(\frac{x_1}{x_2}\) which is primitive
+recursive by the proof found on page 56 of the book.
+\item Let \(m(x_1, x_2) = x_1 * x_2\) which is primitive recursive by proofs in class.
+\item Then \(lcm(x_1, x_2) = floordiv(m(x_1, x_2), gcd(x_1, x_2))\) which is an application of composotion of primitive recursive functions.
+\end{enumerate}
+
+Then \(lcm\) is primitive recursive.
+
+
+\section{Appendix}
+\label{sec:org7f26251}
+\begin{verbatim}
+const isPrime = (n) =>
+  !Array(Math.ceil(Math.sqrt(n)))
+    .fill(0)
+    .map((_, i) => i + 2) // first prime is 2
+    .some((i) => n !== i && n % i === 0);
+
+const primesCache = [2];
+const p = (i) => {
+  if (primesCache.length <= i) {
+    let x = primesCache.at(-1);
+    while (primesCache.length <= i) {
+      if (isPrime(++x)) primesCache.push(x);
+    }
+  }
+  return primesCache.at(i - 1);
+};
+
+const lr = (z, maxSearch = 100) => {
+  let x = 0;
+  for (let i = 0; i < maxSearch; ++i)
+    if ((z + 1) % Math.pow(2, i) === 0) x = Math.max(i, x);
+
+  const y = ((z + 1) / Math.pow(2, x) - 1) / 2;
+  return { l: x, r: y };
+};
+
+const access = (x, i) => {
+  if (i === 0 || x === 0) return 0;
+
+  const p_i = p(i);
+  let minT = x;
+  for (let t = x; t >= 0; t--)
+    if (x % Math.pow(p_i, t + 1) !== 0) minT = Math.min(t, minT);
+  return minT;
+};
+
+const length = (x) => {
+  let minI = x;
+  for (let i = x; i >= 0; i--)
+    if (
+      access(x, i) !== 0 &&
+      Array(x)
+        .fill(0)
+        .map((_, j) => j + 1)
+        .every((j) => j <= i || access(x, j) == 0)
+    )
+      minI = Math.min(i, minI);
+
+  return minI;
+};
+\end{verbatim}
+\end{document}
\ No newline at end of file