1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
% 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}
|
