Math 559: Recursion Theory

Math 559 is an introductory graduate-level course on recursion theory, a.k.a., computability theory.

My plain text advertisement for Math 559 is here.

I taught Math 559 in Spring 2013. We met Mon-Wed-Fri 10:10-11:00 in 106 McAllister. Office hours were Mon-Wed-Fri 11:00-11:30 in 305 McAllister.

• Homework #1: Write a register machine program to prove that the exponential function exp : N x N --> N given by exp(m,n)=m^n is computable. Due Wednesday January 9.
• Homework #2: Let A be a set of natural numbers. Prove that A is computable if and only if A is finite or the principal function of A is computable. The principal function is defined by pi_A(n) = the nth element of A. Due Wednesday January 16.
• Homework #3: Prove the theorem on course-of-values recursion: If h(---,n,z) is computable then so is f(---,n) defined by f(---,n) = h(---,n,z) where z = the prime power code of the sequence f(---,0), ..., f(---,n-1). Due Friday January 18.
• Homework #4: Prove that a real number r is computable if and only if the function f(n) = the nth decimal digit of r is computable. Due Friday January 18.
• Homework #5: Prove that if r and s are computable real numbers then so are r+s, r-s, rs, and r/s. Due Friday January 18.
• Homework #6: Let A be a set of natural numbers. Prove that the following are pairwise equivalent.
  • A is the domain of a partial recursive function.
  • A is the range of a partial recursive function.
  • A is empty or the range of a total recursive function.
  • A is finite or the range of a one-to-one total recursive function.
  • A is Sigma^0_1, i.e., A = { m | exists n R(m,n) } for some recursive predicate R.
  • A is many-one reducible to K.
  • A is many-one reducible to H.
  Due Friday February 1.
• Homework #7: Let H_n = { e | phi_e(0) = n }. Prove that H_1 and H_2 are recursively inseparable. Indeed, H_m and H_n are recursively inseparable whenever m is not equal to n. Due Friday February 1.
• Homework #8: Prove (1) A is many-one-reducible to A', (2) A Turing reducible to B implies A' many-one reducible to B'. Due Wednesday February 6.
• Homework #9: Prove: for every Turing degree c greater than or equal to 0' we can find incomparable Turing degrees a, b such that sup(a,b)=c and inf(a,b)=0. Due Wednesday February 13.
• Homework #10: Prove that a k-place function f(---) is Delta^0_2 if and only if there exists a (k+1)-place computable function g(---,s) such that f(---) = lim_s g(---,s) for all ---. Due Friday March 1.
• Homework #11: Find three distinct natural numbers a, b, c such that phi_a(0) = b, phi_b(0) = c, phi_c(0) = a. Generalize to n distinct natural numbers a_1, ..., a_n. Due Friday March 1.
• Homework #12: Prove that certain parts of Post's Theorem apply to predicates on the Baire space. Specifically, prove the following statements. (1) R is Delta^0_1 relative to g if and only if R is g-recursive. (2) For each nonnegative integer l, if R is Sigma^0_1 relative to the l-th Turing jump of g then R is Sigma^0_l+1 relative to g. (However, the converse does not hold, even for l = 1.) Due Friday March 1.
• Homework #13: Given X and Y in the Cantor space, define Z(2n) = X(n) and Z(2n+1) = Y(n) for all n. Prove that if Z is random then X and Y are Turing incomparable, i.e., X is not computable from Y and Y is not computable from X. Due Wednesday March 20.
• Homework #14: Let l be a positive integer. Using a universal Sigma^1_l predicate, find (1) a set of natural numbers which is Sigma^1_l and not Pi^1_l, and (2) a set in the Baire space which is lightface Sigma^1_l and not boldface Pi^1_l. Due Wednesday April 3.
• Homework #15: Let C and K denote plain and prefix-free Kolmogorov complexity, respectively. Prove the following statements, where < is modulo an additive constant. Statement 1: K(|tau|) < K(tau). Statement 2: C(tau) < K(tau) < C(tau) + K(|C(tau)|). Statement 3: K(n) < 2 log_2 n, K(n) < log_2 n + 2 log_2 log_2 n, K(n) < log_2 n + log_2 log_2 n + 2 log_2 log_2 log_2 n, etc. A hint for statement 3 is: Describe tau as rho^sigma where rho is a prefix-free description of |sigma| and sigma is a description of tau. Due Friday April 26.

Also of interest is the Penn State Logic Seminar.

t20@psu.edu / 30 April 2013