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.

### Like this:

Like Loading...

*Related*

This entry was posted on January 9, 2007 at 8:33 pm and is filed under 117b, Turing degrees. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply