Homework 1
Problem 1.
Show that it is undecidable, given the source code for two programs
\(\Pi\) and
\(\Psi\), to tell whether
\(\Pi\) and
\(\Psi\) are equivalent.
Two programs are equivalent if for all inputs \(x\), either \(\Pi(x)\) and
\(\Psi(x)\) both halt and return the same answer, or neither of them
halts.
Prove this by reducing Halting to this problem. In other words, show
how to convert an instance \((\Pi, x)\) of Halting to an instance
\((\Pi', \Psi)\) of this problem.
Problem 2.
Prove
Rice's Theorem:
Let \(P\) be a property of programs that depends only on the partial
functions that they compute. Assume that there is at least one
program \(\Pi_{1}\) for which \(P\) is true, and at least one program
\(\Pi_{2}\) for which \(P\) is false. Then it is undecidable, given a
program \(\Pi\), to tell whether \(P\) is true for \(\Pi\) or not.
Problem 3.
Show that the
generalized inverse of a primitive recursive
function is primitive recursive.
More precisely, let \(g(y)\) and \(t(x)\) be primitive recursive
functions, and consider the following function:
\[
f(x) := \max \{ y \mid y \leq t(x) \text{ and } g(y) \leq x\}.
\]
Show that
\(f(x)\) is primitive recursive.
Use this to argue that the binary logarithm (\(l(x) = \lfloor
\log_{2}(x)\rfloor\)) and integer division (\(div(x,y) = \lfloor x / y
\rfloor)\) are primitive recursive.
Problem 4.
Imagine computing a function
\(f(x)\) in the following way.
We give an input
\(x\) to a BLOOP program
\(\Pi\), which prints out
another BLOOP program
\(\Pi_x\). We then run
\(\Pi_x\) (a program without
input), which produces
\(f(x)\).
Show that the class of functions that can be computed in this way is
larger than the primitive recursive functions.
Problem 5.
List all pairs
\((x,y)\) for which
\(A_4(x, y)\) does not exceed
\(2^{64}\). Which is larger,
\(A_{4}(5,2)\) or
\(A_{5}(4, 2)\)?