MATH 457: Introduction to Mathematical Logic

Homework #6

Due April 9, 2012

1. Write a register machine program which computes the total function f(m, n) = m^{n}. (Recall that m^{0} = 1 for all m including m = 0.)

2. Write register machine programs which compute the following functions.

(a) ψ_{1}(m, n) = \{ \begin{matrix}q if m = qn where q ∈ ℕ and 0 < n, \\ undefined otherwise. \end{matrix}

(b) ψ_{2}(m, n) = \{ \begin{matrix}q if m = qn where q ∈ ℕ and 0 < n, \\ 0 otherwise. \end{matrix}

(c) ψ_{3}(m, n) = \{ \begin{matrix}q if m = qn + r where q, r ∈ ℕ and 0 ≤ r < n, \\ undefined if n = 0. \end{matrix}

Note: Roughly speaking, for all m, n ∈ ℕ we have ψ_{1}(m, n) = ψ_{2}(m, n) = ψ_{3}(m, n) = the quotient of m on division by n. However, there are significant differences among these three functions.

3. Define

h(n) = \{ \begin{matrix}n/2 & if n is even, \\ 3n + 1 & if n is odd. \end{matrix}

Using primitive recursion, define f(m, i) = h^{i}(m) as follows:

\begin{aligned}f(m, 0) & = & m, \\ f(m, i + 1) & = & h(f(m, i)). \end{aligned}

Finally, define ψ(m) = the least i such that h^{i}(m) = 1.

Write a register machine program which computes ψ.

Note: It is unknown whether ψ(m) is defined for all m ≥ 1. This is a famous open problem in mathematics.