Talk:Turing degree

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

B+ Class

Mid Priority

Field: Foundations, logic, and set theory

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
Geometry guy 23:09, 9 June 2007 (UTC)

How does the Turing degree relate to other measures of computability, such as the arithmetical, analytical, or polynomial hierarchy? The answer to "Post's problem", mentioned in the article, indicates that there are Turing degrees between the recursive problems and the halting problem, but how do these in-between degrees map onto the arithmetical, analytical, or polynomial hierarchies? Does anyone know? (I apologize if my question is confused, btw). Thank-you to anyone who answers! :-)

The polynomial hierarchy is entirely computable (it is a hierarchy of complexity, not computability), so it does not relate in any interesting way to Turing degrees. The arithmetical and analytical hierarchies, on the other hand, are directly related to Turing degrees. I don't have the time or the material (at hand or in memory) to write the details here, but basically, if I am not mistaken, a set is arithmetical iff it is computable from a finite interation of the Turing jump (starting with recursive sets); Post's problem is at level 1 of the arithmetical hierarchy, it is simply not universal for it (so it is not the Turing jump of 0). The analytical hierarchy is more complicated to understand in such terms, but it is also closely related. For more details, see the final chapters in Roger's book (ISBN 0262680521). --Gro-Tsen 02:58, 30 Apr 2005 (UTC)

:I only had time to check this again now. Thank-you, Gro-Tsen!

[edit] plans for clean up

This article is listed as needing cleanup. Since it is such a well-known topic, not just in mathematics but in computer science, some discussion before editing is probably worthwhile. Here is a possible outline for an improved version.

Intro paragraph
Definition of Turing reducibility and Turing degree. C.e. degrees.
Semilattice operations; ideals.
Survey of structural properties. With references to nontrivial results.
Post's problem; the priority method. Nontechnical overview of this classical topic.
Important results. Statements only. References to published surveys.
Other degree structures.
References.

I also think we could redirect [Post's problem] to this page, after the edit.

I hope that someone else has some opinions about what should go in this article. CMummert 18:44, 13 June 2006 (UTC)

I have now implemented some of the ideas above. I removed the cleanup tag, because I think that I have accomplished that goal. Once more articles about degree structures are available, I will add some links to them. I decided not to include ideals because any nontrivial discussion of them would be too technical, and I was hoping to get the article to a level that is readable by someone who took an undergrad CS course in computability.

I intentionally used HTML entities instead of TeX so that the article would be more readable; please discuss before changing everything to TeX. CMummert 14:34, 28 June 2006 (UTC)

[edit] Great work!

Thanks to CMummert for rewriting this article! I very much enjoyed reading it. One minor point: could you clarify what is meant by "Not all finite lattices can be embeded in the r.e. degrees." (naïvely, one might wonder whether the "embedding" is supposed to preserve meets and joins or just the partial order). --Gro-Tsen 15:39, 8 July 2006 (UTC)

[edit] Confusing

I think this article could use a brief introduction explaining in simple mathematical language what precisely is being described here. I am hardly math- illiterate, but this was very difficult to understand. I would appreciate it if this article could be clarified and introduced better. Thanks RSido 03:20, 30 January 2007 (UTC)

Thanks for the comment. I still don't see quite which sections of the article you're asking about ("the whole thing" isn't helpful). Is the first section, entitled Turing equivalence, readable? If not, why not? Is there another section you had in mind? CMummert · talk 03:34, 30 January 2007 (UTC)

I edited the introduction. Absent any more specific comments, I'll remove the {{confusing}} template in a few days. CMummert · talk 04:39, 1 February 2007 (UTC)