# 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)$$?