Midterm Exam #2 – MATH 457 Stephen G. Simpson April 13, 2012

This is a 50-minute exam. While taking this exam, you may not consult any books, notes, or electronic devices.

1. Write a register machine program which computes the 1-place numbertheoretic function F (n) = the nth Fibonacci number. The precise definition of F is as follows:

F (0) = F (1) = 1, F (n + 2) = F (n) + F (n + 1).

2. Consider the 1-place partial number-theoretic function ψ(n) = n/p where p is the largest prime divisor of n. Prove that ψ is partial computable.

Notes:

(a) There is no need to write a register machine program.

(b) In your proof that ψ is partial computable, you may use known lemmas and theorems, for instance our lemmas concerning bounded quantification, the least number operator, etc.

(c) ψ(0) and ψ(1) are undefined.

3. Write a sentence A such that the spectrum of A is the set of powers of two. In other words, your sentence should have the property

spec(A) = {2^{n} | n = 0, 1, 2, …} = {1, 2, 4, 8, 16, …}.