## Computability Theory – Decidability (Caltech, Spring 2007)

Tuesdays, Thursdays 2:30-4:00 pm – 159 Sloan

Syllabus:

This course concludes the introduction to the basic mathematical theory of computation. Two main topics will be covered: We will present examples of decidable theories and problems, arising both in logic and computer science, and in other areas of mathematics. A few additional logic tools will be introduced (e.g., quantifier elimination) that will prove useful in establishing that particular problems are decidable. We will also pay particular attention to issues of computational complexity, and discuss in some detail the P vs. NP problem. Depending on time, we may also present an introduction to the theory of algorithmic randomness.

Grading will be based on Homework assignments. There will be no exams.

Solutions to homework problems should be written individually, although collaboration is allowed. All references used to solve a problem should be explicitly mentioned, including those students you collaborated with. However, you cannot look up solutions from any source (including other students, earlier years’ solution sets, books, etc).

No late submissions of solutions are allowed, except for medical problems (note needed from the health center) or serious personal difficulties (note needed from the Dean’s office).

Please, and this is very important, make sure that what you turn in is your final solution, as opposed to a draft or your scratch work. Be neat and professional about the appearance of your work. However, if you cannot find a complete solution to a problem, turn in a partial solution, indicating what is missing. Again, this does not mean that you can turn in your scratch work for problems you only have partially completed, but make clear at the beginning of your solution that you did not finish the problem.

Homework:

Update:  I’ve been exchanging emails with a few people about problem 2.(b). This is what came out of it:

The problem comes from a book by Barry Cooper. I started to suspect yesterday that there was a typo (after seeing how my sketch couldn’t be fleshed out into a full argument), and was just searching for something like Degtev’s result (see below) in a few books (without success).

Orestis found the following: Degtev proved that there are tt-degrees containing only one r.e. m-degree. There is a proof of this result (due to Downey) that gives such a degree as the degree of a simple set.

Some definitions:

• 1-reducible means many-one reducible but the witnessing function f is not only recursive but also injective.
• m-reducible means many-one reducible.
• tt stands for truth table; we do not need the definition at the moment, but tt-reducibility is a more general notion than m-reducibility but less general than Turing reducibility.

Say A is m-equivalent to B iff it is m-reducible to B and vice versa. Similarly define tt-equivalent, 1-equivalent, etc. These are equivalence relations, the corresponding equivalence classes are the 1-degrees, m-degrees, etc. We have:

1.  A 1-reducible to B implies A m-reducible to B, trivially.
2.  A m-reducible to B implies A tt-reducible to B.
3.  A tt-reducible to B implies A Turing-reducible to B.

A degree is r.e. if one of the elements of the equivalence class is an r.e. set.

I was a bit worried, since inside any non-recursive tt-degree there is an infinite antichain of many-one degrees (though many of them are not r.e.); this is a result of Stephan.

(Downey’s version of) Degtev’s result gives that there is a simple set S such that if X is r.e. and tt-equivalent to S then X is m-reducible to S. If X is a theory (X=Th(X)), then this gives a counterexample to the problem.

Now, for any r.e. set X there is a theory T(X) such that X 1-1 reduces to T(X) and T(X) truth-table reduces to X (Feferman). So we have indeed a counterexample to the problem as stated.

The annoying thing that had me stumped is that there are theories T’(X) of the same Turing degree as X (for any r.e. set X) that are essentially undecidable (Shoenfield) and therefore are part of a recursively inseparable pair, so I didn’t have much hopes for something like Degtev’s result.  Many thanks to Orestis for looking into this, and sorry for the headaches the problem may have caused you.

[ There is a reasonable version of 2.(b) which has the advantage of being true. It is posted above and due Thursday. Email me if you don’t remember (or haven’t seen) the definition of Robinson’s Q. You may assume the result of Homework 7.4. from 117b. ]

Update: The result should be that the set $Phi$ of formulas:

• $varphi_n$  (for each n)
• $x=y$

is an elimination set for the class K of all sets (i.e., of all structures in the empty language), where $varphi_n$ is the formula saying that there are at least n elements.

Update: In question 2, $varphi_n$ should be “there are exactly n elements” rather than “at least n.”