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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
% Created 2023-11-11 Sat 20:04
% 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 29.1 (Org mode 9.7-pre)},
pdflang={English}}
\begin{document}
\maketitle
\setlength\parindent{0pt}
\section{Problem One}
\label{sec:org7aa3a78}
Let \(m\) be the number of statements that don't produce an effect on \(Y\) i.e.
\(\{ Y \leftarrow Y, X1 \leftarrow X1 + 1, \cdots \}\), \(n\) be the number of statements \(Y \leftarrow Y - 1\), and
\(o\) be the number of statements \(Y \leftarrow Y + 1\). A straightline program of length \(k\)
must have \(m + n + o = k\) instructions. Then, the terminal snapshot ends with
\(Y = o - n + 0m\). Thus, \(Y\) is at a maximum if and only if \(o = k\), thus \(Y = k\),
and at a minimum if and only if \(o = n\), thus \(Y = 0\) (we cannot have \(n > o\) as
by definition of \(L\), for a valid program \(P\) \(Y\) is a non-negative number).
\section{Problem Two}
\label{sec:orgb9efdfb}
Let \(P\) be a program in \(L\) that computes \(f\). Then \(f\) is partially computable
by definition, and is partially computable in \(L++\) trivially since \(L++\) is a
"superset" of \(L\). (\(L++ \Leftarrow L\)).
Then let \(Q\) be a program in \(L++\) that computes \(f\), \(f\) is partially computable
if we can convert \(Q\) into \(L\). For each instruction \(i \in Q\), if \(i\) is in the form
\(V \leftarrow k | k \in N\) then we replace \(i\) with the sequence of instructions and unique labels
(with the notation \(\cdots{}\) representing a reapeating instruction until the instruction is the
following index), else write \(i\) (\(L++ \Rightarrow L\)).
\begin{verbatim}
1. [A1] IF V != 0 GOTO B1
2. GOTO C1
3. [B1] V <- V - 1
4. GOTO A1
5. [C1] V <- V + 1
... V <- V + 1
(5 + k - 1). V <- V + 1
\end{verbatim}
And thus any program in \(L++\) is also partially computable.
\section{Problem Three}
\label{sec:org53e881b}
For \(n=0\), \(i(n, x) = f^0(x) = x\) is primitive recursive since it can be represented as
a projection function \(u_1^1(x) = x\). If \(f^n\) is primitive recursive, then so is \(f^{n+1}\), as \(f^{n+1}\)
is a finite composition \(f(f^n)\). By induction, for any \(n \in N\), \(i(n, x)\) is primitive recursive, and thus computable.
\section{Problem Four}
\label{sec:orgbc1477c}
\subsection{One}
\label{sec:org96da465}
Let \(m \in N\) represent the number of compositions in a function such that the set containing all \(n\) -ary
functions with "composition number" \(m\) are of the form
\(f(x_1, \cdots, x_n) = g(f_1(x_1, \cdots, x_n), \cdots, f_j(x_1, \cdots, x_n))\)
where each \(f_i\) is in the set of functions with a "composition number" \(\le m - 1\). Except for the case in which
\(m = 0\) - the initial functions; which are all of the form \(k\) or \(x_i + k\).
Then, let \(F^m | m \in N\) represent the set of all functions of composition number \(m\) or less,
and assume that \(\forall f \in F^m\) are of either form \(k\) or \(x_i + k\). Then, \(g \in F^{m+1} | m \in N\)'s elements
are \(g(x_1, \cdots, x_n) = f(f_1(x_1, \cdots, x_n), \cdots, f_j(x_1, \cdots, x_n))\) where \(f\) is an initial function, by definition, and each
\(f_i | 1 \le i \le j \in F^m\).
\begin{enumerate}
\item If \(f\) is the Zero function \(g\) is in the form \(k = 0\)
\item If \(f\) is the Successor function \(g\) is some \(f_i(\cdots) + 1\) which by assumption is thus \((x_i + k) + 1 \Rightarrow x_i + k\) or \(k + 1 \Rightarrow k\).
\item If \(f\) is the Projection function \(g\) is some \(f_i(\cdots)\) which by assumption is \((x_i + k)\) or \(k\).
\end{enumerate}
Finally, by induction, \(\forall f(x_1, \cdots, x_n) \in\) \texttt{COMP}, \(f\) is thus in the form \(k\) or \(x_i + k | 1 \le i \le n\).
\subsection{Two}
\label{sec:org74c3eb4}
By what we showed in One, \(f(x_1, \cdots, x_n)\) is dependent on a single \(x_i \in {x_1, \cdots, x_n}\) and produces \(r = (x_i + k)\) or \(r = k\). Then \(f(y_1, \cdots, y_n) = (y_i + k) | k\)
for the same \(i\). So if for all \(i | 1 \le i \le n\), \(x_i \le y_i\) then \((y_i + k) \ge (x_i + k)\) or \(k = k\). Thus in both cases \(f(y_1, \cdots, y_n) \ge f(x_1, \cdots, x_n)\)
and is thus monotonic.
\subsection{Three}
\label{sec:org8b3878c}
Yes. Firstly, every \(f \in\) \texttt{COMP} is primitive recursive, just without the recursion, so it is a subset of the set of all primitive recursive
functions.
Consider the (proven in class) primitive recursive function \(f(x_1, x_2) = x_1 * x_2\), and the equivalent \(g \in\) \texttt{COMP}. \(g(x_1, x_2)\) is equivalent to
\(x_1 + k\), \(x_2 + k\), or \(k\). Then there all elements of \(\{f(x_1, x_2 + 1), f(x_1 + 1, x_2), f(x_1, x_2)\} | x_1, x_2 > 1\) cannot be present in
\(\{g(x_1, x_2 + 1), g(x_1 + 1, x_2), g(x_1, x_2)\}\) for the same \(x_1, x_2\) due to the dependence relation, which is a contradiction to \(f\) and \(g\)
being equivalent.
\subsection{Four}
\label{sec:orgcea60eb}
Yes. By the fact that all primitive recursive functions are computable, \texttt{COMP} being a set of primitive recursive functions from Three, is a subset of computable functions.
However, we also showed in Three that there exists a computable (primitive recursive) function which is not in \texttt{COMP}, so \texttt{COMP} is not equivalent to the set
of all computable functions.
\section{Problem Five}
\label{sec:orgab79ce2}
\begin{enumerate}
\item Let \(a(x_1, x_2) = x_1 + x_2\) and \(m(x_1, x_2) = x_1 * x_2\) which are primitive recursive by proofs in class.
\item Let \(t(x_1)\) be the composition of the successor function \(s\) 10 times on the zero function \(z\) function: \(t(x_1) = s(s(\cdots(n(x_1))))\), and is primitive recursive.
\item Let \(v(x_1)\) be \(v(x_1) = a(x_1, a(x_1, a(x_1, a(x_1, u_1^1(x_1)))))\), which is primitive recursive.
\item Let \(w(x_1)\) be \(w(x_1) = a(t(x_1), v(x_1))\), which is primitive recursive.
\item Let \(y(x_1)\) be \(y(x_1) = m(m(x_1, x_1), s(s(n(x_1))))\), which is primitive recursive.
\item Then \(f(x_1)\) is \(a(w(x_1), y(x_1))\), which is primitive recursive.
\end{enumerate}
\end{document}
|
