From 6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6 Mon Sep 17 00:00:00 2001 From: Elizabeth Alexander Hunt Date: Thu, 2 Jul 2026 11:55:17 -0700 Subject: Init --- Homework/cs5000/midterm02/compile_l_program.js | 0 Homework/cs5000/midterm02/midterm.org | 218 ++++++++++++++++++++ Homework/cs5000/midterm02/midterm.pdf | Bin 0 -> 301405 bytes Homework/cs5000/midterm02/midterm.tex | 265 +++++++++++++++++++++++++ Homework/cs5000/midterm02/p1.png | Bin 0 -> 130008 bytes Homework/cs5000/midterm02/p2.png | Bin 0 -> 80178 bytes 6 files changed, 483 insertions(+) create mode 100644 Homework/cs5000/midterm02/compile_l_program.js create mode 100644 Homework/cs5000/midterm02/midterm.org create mode 100644 Homework/cs5000/midterm02/midterm.pdf create mode 100644 Homework/cs5000/midterm02/midterm.tex create mode 100644 Homework/cs5000/midterm02/p1.png create mode 100644 Homework/cs5000/midterm02/p2.png (limited to 'Homework/cs5000/midterm02') 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 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 Binary files /dev/null and b/Homework/cs5000/midterm02/midterm.pdf differ 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 Binary files /dev/null and b/Homework/cs5000/midterm02/p1.png differ diff --git a/Homework/cs5000/midterm02/p2.png b/Homework/cs5000/midterm02/p2.png new file mode 100644 index 0000000..afab994 Binary files /dev/null and b/Homework/cs5000/midterm02/p2.png differ -- cgit v1.3