InitHEADmain

6 files changed, 483 insertions, 0 deletions

diff --git a/Homework/cs5000/midterm02/compile_l_program.js b/Homework/cs5000/midterm02/compile_l_program.js
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/Homework/cs5000/midterm02/compile_l_program.js
diff --git a/Homework/cs5000/midterm02/midterm.org b/Homework/cs5000/midterm02/midterm.org
new file mode 100644
index 0000000..7d1312f
--- /dev/null
+++ b/Homework/cs5000/midterm02/midterm.org
@@ -0,0 +1,218 @@
+#+TITLE: HW 08
+#+AUTHOR: Elizabeth Hunt (A02364151)
+#+STARTUP: entitiespretty fold inlineimages
+#+LATEX_HEADER: \notindent \notag  \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
+#+LATEX: \setlength\parindent{0pt}
+
+* Problem One
+#+attr_latex: :width 7cm
+[[./p1.png]]
+
+* Problem Two
+#+attr_latex: :width 7cm
+[[./p2.png]]
+
+* Problem Three
+Using the following code proceeding the appendix we receive
+
+$l(111) = 4$
+
+$r(111) = 3$
+
+$lt(111) = 12$
+
+#+BEGIN_SRC js
+  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_SRC
+
+* Problem Four
+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_SRC js
+  const p4 = () => {
+    const x = 17;
+
+    for (let i = 0; i <= 8; i++) 
+      console.log(`(${x})_${i} = ${access(x, i)}`)
+  };
+  p4();
+#+END_SRC
+
+
+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$.
+
+* Problem Five
+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$.
+
+* Problem Six
+** \phi_5^1(x)
+\phi_5^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}
+
+** \phi_7^1(x)
+\phi_7^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}
+
+** \phi_11^1(x)
+\phi_11^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_5^1(x):
+
+\begin{verbatim}
+Y <- Y + 1
+[ A1 ] Y <- Y
+\end{verbatim}
+
+** \phi_13^1(x)
+\phi_13^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 ~Y <- Y~ (unlabeled, $\#(V) = 0$, op = 0).
+
+\begin{verbatim}
+[ A1 ] Y <- Y
+Y <- Y
+Y <- Y
+[ A1 ] Y <- Y
+\end{verbatim}
+
+** \phi_17^1(x)
+\phi_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_11^1(x)
+
+\begin{verbatim}
+[ A1 ] Y <- Y
+Y <- Y + 1
+\end{verbatim}
+
+* Problem Seven
+1. Let $m(x_1, x_2) = x_1 * x_2$ which is primitive recursive by proofs in class.
+2. Let $four(x_1) = s(s(s(s(n(x_1)))))$; the successor function composed 4 times on the null function.
+3. Then $f(x_1)$ is $m(four(x_1), x_1)$ which is an application of composition of primitive recursive functions.
+
+Thus, $f$ is primitive recursive, and thus computable.
+
+* Problem Eight
+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$.
+
+1. Define $gcd(x_1, 0) = x_1$
+2. 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.
+3. We construct the informal recursion $gcd(x_1, x_2) = gcd(x_2, R(x_1, x_2))$ by Euclid's Algorithm.
+4. 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.
+5. Let $m(x_1, x_2) = x_1 * x_2$ which is primitive recursive by proofs in class.
+6. 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.
+
+Then $lcm$ is primitive recursive.
+
+
+* Appendix
+#+BEGIN_SRC js
+  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_SRC
diff --git a/Homework/cs5000/midterm02/midterm.pdf b/Homework/cs5000/midterm02/midterm.pdf
new file mode 100644
index 0000000..f79a624
--- /dev/null
+++ b/Homework/cs5000/midterm02/midterm.pdf
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
diff --git a/Homework/cs5000/midterm02/p1.png b/Homework/cs5000/midterm02/p1.png
new file mode 100644
index 0000000..31740b9
--- /dev/null
+++ b/Homework/cs5000/midterm02/p1.png
diff --git a/Homework/cs5000/midterm02/p2.png b/Homework/cs5000/midterm02/p2.png
new file mode 100644
index 0000000..afab994
--- /dev/null
+++ b/Homework/cs5000/midterm02/p2.png