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)\)?