Talk:Turing degree

Untitled

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!

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)

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)

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)

Turing degrees densely ordered?

This article makes the claim that Turing degrees are not densely ordered. But in his review of A New Kind of Sceince (http://www.rudyrucker.com/pdf/wolfram_review.pdf), Rudy Rucker states that "not only are the Turing degrees densely ordered, they fail to be linearly ordered" (page 858). I take the latter to be an indication that they are partially ordered, but the former seems to contradict this article pretty directly. Anyone have any insights about this problem? Am I misreading something? Solemnavalanche (talk) 16:21, 8 December 2008 (UTC)

It's a theorem of Clifford Spector that there is a minimal non-zero Turing degree. That is to say that there is a set M such that M is not recursive and for any X recursive in M, either M is recursive in X or X is recursive. Consequently, the Turing degrees are not densely ordered. Mon_oncle (talk) 16:41, 8 December 2008 (UTC)

I'll take your word that it's a theorem, but in that case, what did Rucker mean? Perhaps he meant that some subsets of the Turing degrees are densely ordered? That seems to be implied later in this article (in the section on r.e. degrees). I'm just confused because, you know, it's in a peer reviewed journal and all, even if that particular article may not have been subjected to strict peer review.

Also, If my inference is correct (i.e. that the Turing degrees are not densely ordered, but include densely ordered subsets), shouldn't it be explicitly stated in the article somewhere? Solemnavalanche (talk) 17:08, 8 December 2008 (UTC)

The Sacks Density Theorem asserts that the Turing degrees of the recursively enumerable sets are dense. Possibly, that is what is meant in the Rucker article, but the article is incorrect as written. Mon_oncle (talk) 17:42, 8 December 2008 (UTC)

0″

On Computable number page it is said that decision problem "Given Turing machine, determine whatever it computes total function" is Turing degree 0″. Is it true? Maybe it is truly degree 0′ 83.23.20.209 (talk) 16:56, 19 March 2012 (UTC)

[Be careful about using double-prime in Wiki markup, as it is considered to be a mark of italics. I fixed your question.]
Yes, it is true. Determining whether a Turing machine computes a total function is a ∀∃ (i.e., Π₂) type question, because one must decide whether for all input there exists an execution trace showing that the machine halts, and it is pretty obvious that any ∀∃ question can be reduced to this kind; now the halting problem for 0′, that is 0″, is ∃∀, because to say that a 0′ machine halts means that there exists an execution trace showing that for all "does not halt" reply the halting oracle gave the corresponding Turing machine indeed does not halt (for all time). So this halting problem can be reduced to asking whether a certain Turing machine does not compute a total function. There is probably a more intuitive way of saying it which makes the Turing machine more explicit, but 0″ is undoubtedly the correct degree. --Gro-Tsen (talk) 12:01, 20 March 2012 (UTC)

Not a lattice?

The article currently states There are pairs of degrees with no greatest lower bound. Silly me, I don't understand. Isn't every degree greater than zero? User: Linas (talk) 03:05, 3 September 2013 (UTC)

0 is always a lower bound, but in general not the greatest lower bound (=infemum). --Gro-Tsen (talk) 11:53, 5 September 2013 (UTC)

Dohh, thanks. I wonder how this could be clarified; it seems like an important point. User: Linas (talk) 17:32, 2 November 2013 (UTC)

Not every degree less than 0′ is an r.e. degree.

Who did prove that and when? --Jobu0101 (talk) 18:01, 28 April 2015 (UTC)

Is this an example of intermediate turing degree problem?

• https://cs.stackexchange.com/questions/92503/how-strong-consistent-guessing-problem-is
• http://people.csail.mit.edu/andyd/cg.pdf
• https://www.scottaaronson.com/blog/?p=710

If so, should that be placed on the page as an example of such a problem that has intermediate Turing degree? --70.31.88.62 (talk) 22:08, 3 March 2019 (UTC)

The consistent guessing problem is a set of languages; some of these languages have intermediate degree, but others have the same degree as the halting problem. So probably not worth mentioning as an example of intermediate degree, although it might be worth mentioning as a "zero injury" proof. (Actually, it's not clear to me that the language in question is computably enumerable, or even that it is reducible to the halting problem. So it might not have intermediate degree.) Ben Standeven (talk) 08:31, 21 December 2020 (UTC)

Result contradicting quote in article?

I might be wrong but I think I have found a result refuting a sentence from the Order properties section. The article says "no infinite, strictly increasing sequence of degrees has a least upper bound", but supposedly Sacks's Degrees of Unsolvability (1963) proves that any countable set of Turing degrees has a minimal upper bound. (I don't have a copy of the original, I got this citation via a reference from Maximal Chains in the Turing Degrees.) If we were to take some countable strictly increasing chain of degrees, and look at the set of members of that sequence, by Sacks wouldn't it have a least upper bound? C7XWiki (talk) 02:26, 12 October 2022 (UTC)

For an infinite strictly increasing sequence of Turing degrees, a minimal upper bound always exists, but is never unique, hence there is no least upper bound. I added a sentence to that effect to the article. Dmytro (talk) 03:53, 12 October 2022 (UTC)