% Created 2023-11-04 Sat 18:02
% 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 07}
\hypersetup{
 pdfauthor={Elizabeth Hunt (A02364151)},
 pdftitle={HW 07},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 28.2 (Org mode 9.7-pre)}, 
 pdflang={English}}
\begin{document}

\maketitle
\setlength\parindent{20pt}

\section{Problem One}
\label{sec:orgd2348b9}

\begin{verbatim}
1. [A1] Y  <- Y  - 1
2.      IF Y  != 0 GOTO A
3. [B1] IF X1 != 0 GOTO C
4.      GOTO E
5. [C1] X1 <- X1 - 1
6.      Y  <- Y  + 1
7.      Y  <- Y  + 1
8.      Y  <- Y  + 1
9.      GOTO B1
\end{verbatim}

\section{Problem Two}
\label{sec:org07c7432}
\begin{enumerate}
\item \((1, \sigma) | \sigma = \{X_1 = 2, Y = 0, Z_1 = 0\}\)
\item \((4, \sigma) | \sigma = \{X_1 = 2, Y = 0, Z_1 = 0\}\)
\item \((5, \sigma) | \sigma = \{X_1 = 1, Y = 0, Z_1 = 0\}\)
\item \((6, \sigma) | \sigma = \{X_1 = 1, Y = 1, Z_1 = 0\}\)
\item \((7, \sigma) | \sigma = \{X_1 = 1, Y = 1, Z_1 = 1\}\)
\item \((1, \sigma) | \sigma = \{X_1 = 1, Y = 1, Z_1 = 1\}\)
\item \((4, \sigma) | \sigma = \{X_1 = 1, Y = 1, Z_1 = 1\}\)
\item \((5, \sigma) | \sigma = \{X_1 = 0, Y = 1, Z_1 = 1\}\)
\item \((6, \sigma) | \sigma = \{X_1 = 0, Y = 2, Z_1 = 1\}\)
\item \((7, \sigma) | \sigma = \{X_1 = 0, Y = 2, Z_1 = 2\}\)
\item \((1, \sigma) | \sigma = \{X_1 = 0, Y = 2, Z_1 = 2\}\)
\item \((2, \sigma) | \sigma = \{X_1 = 0, Y = 2, Z_1 = 2\}\)
\item \((3, \sigma) | \sigma = \{X_1 = 0, Y = 2, Z_1 = 3\}\)
\item \((8, \sigma) | \sigma = \{X_1 = 0, Y = 2, Z_1 = 3\}\)
\end{enumerate}

\section{Problem Three}
\label{sec:orgf9c18d1}
\begin{verbatim}
1. [A1] Y  <- Y
2.      Y  <- Y
3.      Y  <- Y
4.      Y  <- Y
5.      Y  <- Y
6.      GOTO E
\end{verbatim}

\section{Problem Four}
\label{sec:org49ea029}
Let \(P\) be a program in \(L\) that computes \(g(x_1, x_2, \cdots, x_n)\); a list of instructions \([I_1, I_2, \cdots, I_k]\),
where \(I_1\) is the first instruction and \(I_k\) the last.

Then, define \(P^i | i \in N\) to be a new program such that each instruction \(I_n\) replaces \(I_{n+i}\) (when \(n=0\)
we perform no operation), appending
to the end of the instruction list if necessary. We then replace the sublist \([I_1, \cdots, I_i]\) with
\([Y \leftarrow Y]^i\) in the program \(P\). As \(Y \leftarrow Y\) produces no side effects then \(P^i\) still computes \(g\).

Finally, for all \(i \in N\) the length of \(P^i\) is greater than \(k\) and thus there are countably infinitely
many \(L\) -programs to compute \(g\).
\end{document}