path: root/Homework/cs5000/midterm02/midterm.tex

% 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}