These notes are mostly from 2004 but some addtions from 2007.

Lecture notes for Recursion Theorists:

recthy.tex ..
recthy.pdf

Version for Computability Theorists:

cmpthy.tex ..
cmpthy.pdf

Version for for those who love pineapples:

pineapp.tex ..
pineapp.pdf

Math 773 Fall 2007 Computability

A.Miller homepage ... old web sites

M773 Fall 2007 MWF 12:05-12:55 Van Vleck B131

Recommended books:

Hartley Rogers, Theory of recursive functions

Robert Soare, Recursively enumerable sets and degrees

Barry Cooper, Computability theory

DESCRIPTION: Abstract theory of computation. Turing degree and jump, strong reducibilities, arithmetic hierarchy, index sets, simple and (hyper)hypersimple sets, easy forcing arguments in computability theory, finite injury priority arguments: Friedberg-Muchnik Theorem, Sacks Splitting Theorem, existence of a maximal set. Infinite injury priority arguments: Lachlan minimal pair, Sacks density theorem, incomplete high degrees. Recursive ordinals and the hyperarithmetical hierarchy.

Homework is due in class one week from the
day it is assigned.

1. (Wed 9-5) Email soare@cs.uchicago.edu and request that he
email you a copy of his book.

2. (Fri 9-7) Convince yourself that every computable function
is UR-BASIC computable. Write a UR-BASIC program for d=gcd(n,m).

3. (Mon 9-10) Show that the "dove-tailing" pairing function
is primitive recursive.

4. (Wed 9-12) Let f(n) be the n th digit in the usual
decimal expansion of the square root of 2. Prove that
f is primitive recursive.

5. (Fri 9-14) Show that a UR-Basic computable function which
can be computed in primitive recursive time is primitive recursive.

6. (Fri 9-14) Show that P-Basic computable is the same as
primitive recursive. P-Basic has no goto's but only for-next loops.
(see notes exerise 4.6.)

7. (Mon 9-17) Prove there is a computable function f
whose graph is primitive recursive but f is not primitive recursive.

8. (Wed 9-19) For a partial function f suppose that each of dom(f),
graph(f), and range(f), is either computable or computably enumerable but not
computable. For each of the 8 possibilities, either give an example of such an f
or prove it is impossible.

9. (Fri 9-21) (a) For a partial function f prove that f is
partial computable iff its graph is computably enumerable.
(b) For a partial computable h prove there is a partial computable g
with dom(g) containing range h and for all y in range h h(g(y))= y.
(c) Give an example for (b) for which g cannot be total.

10. (Mon 9-24)(a) Prove there is an e such that
W_e= {0,1,2,..., e^2+1}.
(b) Prove there are distinct e0 and e1 with W_e0={e1}
and W_e1={e0}

11. (Wed 9-26) Prove that a c.e. set A is creative iff there exists
a computable f such that (f(e) in W_e and f(e) in A) or
(f(e) not in W_e and f(e) not in A) for every e.

12. (Fri 9-28) Prove or disprove: there is a creative set A and
computable function f such that for any e, if
W_e meets A in a finite set, then f(e) is not in A or W_e.

13. (Mon 10-1) Suppose A and B are infinite c.e. sets and A one-to-one
reducible to B. Show there is a one-to-one reduction of A to B which maps A
onto B.

14. (Wed 10-3) Show that for any countable set of nonzero Turing
degrees there is a degree incomparable to everything in the set.

15. (Fri 10-5) Prove that: (a) For every degree c there are incomparable
degree a and b which meet in 0 and join above c.
(b) There are incomparable degrees a and b which meet in 0 and join
in 0'.

16. (Mon 10-8) Prove that if two degrees a and b fail to have
a meet then there is a strictly ascending sequence of degrees as in
Spector's Theorem 21.1.

17. (Wed 10-10) Find an example of a computable binary branching subtree of
finite sequences in omega with the property that it has a single infinite branch
b and b is Turing equivalent to K.

18. (Fri 10-12) Prove there is a perfect tree T such that every
infinite branch thru T has minimal degree.

19. (Mon 10-15) Prove that O^(omega) is not a minimal upper bound
of the O^(n).

20. (Wed 10-17) Prove

(a) If A is 1-1 reducible to B and B simple then A is simple or
cofinite.

(b) If A and B simple then A join B simple.

(c) If A and B simple then A intersect B simple.

(d) If A simple, b notin A, and B=A U {b}, then
B <_1 A and nothing is in between.

21. (Fri 10-19) Prove that if A and B are simple incomparable with respect
to 1-reducibility, then A and B have no join with respect to 1-reducibility.
Hint: Use exercise 20 and 13.

22. (Mon 10-22) Prove there is a computable poset in which every countable
poset can be embedded.

23. (Wed 10-24) Prove there are c.e. sets A and B which are Turing
incomparable, disjoint, and cannot be separated by a computable set.

24. (Fri 10-26) Prove there is a c.e. set which is not auto-reducible.
Extra Credit: make it a low simple set.

25. (Mon 10-29) (a) Suppose B is a c.e. set which is not computable.
Prove there exists a partial computable function f with domain B such that
for every n in omega the set f^{-1}{n} is not computable. (b) Prove or
disprove. There exists A_n for n in omega pairwise disjoint c.e. sets which
are not computable and partition omega.

26. (Wed 10-31) Show that if B is c.e. but not computable, then there
exists disjoint c.e. sets C and D with union B which cannot be separated by a
computable set. Hint: If {e} is total, show that there must be infinitely
many s such that {e}_s(b_s) converges.

27. (Fri 11-2) Show there exists low c.e. sets A_0 and A_1 such that
every c.e. B set is Turing equivalent to a join of c.e. sets B_0 and
B_1 where B_i is computable in A_i.

28. (Mon 11-05) Put the Friedberg-Muchnik argument on a tree
of outcomes. Show there is no injury on the true path.

29. (Wed 11-07) Prove there is a minimal pair A_0 and A_1 such
that (a) each A_i is low. (b) A_0 and A_1 are beneath a low B.

30. (Mon 11-12) (a) Prove that truth-table reducibility is
transitive. (b) Prove that if A is hypersimple and
(D_x:x in C ) is a strong array, then there exists an infinite
computable E subset of C such that D_x subset of A for all x in E.

31. (Wed 11-14) Suppose A is a c.e. set with infinite complement.
Prove it has a hypersimple superset.

32. (Fri 11-16) Let A be a maximal set (or just hyperhypersimple).
Let f be a computable map of omega 1-1 onto A. Suppose B=f(A).
Prove that B is hyperhypersimple but not maximal.

33. (Mon 11-19) For each n >1 prove there are maximal sets
A1,A2,...,An such that Ai not equal mod finite to Aj for distinct
i and j. Prove that for any such sequence of maximal sets that
E*(B) is isomorphic to the finite boolean algebra with n atoms
where B is the intersection of them.

34. (Mon 11-26) Prove there is a permuation f of omega such that
for every c.e. set A that f(A) is c.e. but for some c.e. set A
f^-1(A) is not c.e.

35. (Wed 11-28) (Martin) Find an example of a nontrivial c.e. set
which has no maximal superset.

36. (Fri 11-30) Prove that if b(0),b(1),b(2).. is the complement of
a maximal set B,then for every computable f,
f(b(n)) is less than b(n+1) for all but finitely
many n.

37. (Mon 12-03) Suppose for every n that 0^(n) is computable in
A. Prove that 0^(omega) is computable in A''.

38. (Wed 12-05) For the correct family Gamma, show that
INF, EQ, EQ* are m-complete Gamma sets.