Archive for the ‘Turing degrees’ Category

117b – Turing degrees – Lecture 5

January 18, 2007

We finish the first topic of the course with a survey of results about the theory of D.

In particular, we state the Slaman-Woodin theorems on coding countable relations inside D and on the structure of Aut(D).

The coding theorem and the arithmetic definability of <T give a new proof of Simpson’s theorem on the complexity of Th(D): Not only it is undecidable, but it is recursively isomorphic to the theory of second-order arithmetic. That <T is definable in first order arithmetic will be shown as part of the second topic.

The results on Aut(D) give that there are only countably many automorphisms of D, that they are all arithmetically definable, and coincide with the identity above 0². This was then used by Slaman and Shore to prove that the relation R(x,y) iff y=x¢ is definable in D.

We then state Martin’s theorem on Turing Borel determinacy that any degree invariant property which is Borel as a subset of 2N and <T-cofinal holds on a cone.

117b – Turing degrees – Lecture 4

January 16, 2007

We define languages and structures in the model theoretic sense, and the notion of an embedding between structures of the same language.

We prove that the S1 theory of the degrees is decidable by means of forcing:

  • First we reduce the argument to showing that any finite partial order can be embedded in D.
  • Then we argue that for this it is enough to show that there is an infinite independent family of degrees, where independence means that no element of the family is reducible to the join of finitely many of the other members of the family.
  • Finally, we build such a family using forcing.

117b – Turing degrees – Lecture 3

January 11, 2007

We present a general framework for forcing arguments, and give the proof of the existence of incomparable degrees in the language of forcing.

We define the hierarchy of  Sn formulas and define theories, the theory of a structure, and what it means for a theory to be decidable.

We want to show that the S1 theory of D is decidable. For this, we will use the technique of forcing to show that there is an infinite set of independent degrees.

Additional reference:

  • Degree structures: local and global investigations, by R. Shore. Bulletin of Symbolic Logic 12 (3) (2006), 369-389.

117b – Turing degrees – Lecture 2

January 9, 2007

We define the structure D of the Turing degrees as the quotient of the set of functions f:N®N by the equivalence relation ºT of recursive bi-reducibility, seen as a partial order with the order <T induced by Turing reducibility. This structure has a least degree and any degree has only countably many predecessors. It is an upper semilattice, and any countably many degrees have a common upper bound.

Generalizing the halting problem, we can define the Turing jump a¢ of any degree a. It is strictly above a and any A r.e. in a is T-reducible to a¢.

There are incomparable Turing degrees. They can be built by the finite extension method, an example of forcing in recursion theory.

117b – Turing degrees – Lecture 1

January 4, 2007

There are several equivalent characterizations of the notion of being recursive in a function f, namely:

  •  Belonging to the closure of {f} under recursive functions and recursive operations.
  •  Being computable using a Turing machine with oracle f.  

The key tool to use this notion is the enumeration theorem.

This material should just be a generalization of notions and results studied in 117a. The following references may be useful for this part of the course:

  • Mathematical Logic,  part II, by R. Cori and D. Lascar. OUP (2001), 0 -19-850050-5
  • Computability: An introduction to recursive function theory, by N. Cutland. Cambridge Univerity Press (1980), 0-521-294657
  • Theory of recursive functions and effective computability, by H. Rogers. MIT press (1987), 0-262-68052-1
  • Computability theory, by B. Cooper. CRC Press (2003), 1-58488-237-9
  • Degrees of unsolvability: Local and global theory, by M. Lerman. Springer (1983), 0-387-12155-2