# Halting Problem and Turing Degree and Reduction? [closed]

This is a Local Olympiad question on computation and computer science on 2013. How can explain it and says some hint for understanding such an example question.

for $A \subseteq \mathbb{N}$ we have $a=deg_T(A)=\{B | B \equiv_T A \}$ and $D=\{deg_T(A)| A \subseteq \mathbb{N} \}$. For $(D, \leq)$ that has $A \leq_T B$ iff $a \leq b$. which of the following is false:

1) $(D, \leq)$ is a distributive lattice

2) $(D, \leq)$ ‌ is bounded (has minimum and maximum)

3) $(D, \leq)$ is a half disjunctive lattice. (may be I‌ worded this statement poorly, sorry)

4) he maximum elements of $(D, \leq)$ is a degree of Halting Problem .

I think $deg_T$ means Turing Degree and $\leq_T‌$ means Turing Reduciblity.

Edit 1: • What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understaing. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Apr 10 '15 at 11:45
• @Raphael if it's homework, then a fun homework :) – Maryam Panahi Apr 10 '15 at 11:46
• Read a textbook on Turing degrees. The lattice of Turing degrees has a minimum (the recursive degree) but no maximum, since the jump of any degree (i.e., the corresponding halting problem) is larger than the degree. – Yuval Filmus Apr 10 '15 at 16:22
• I gave you an algorithm for finding the answer yourself: consult a textbook on Turing degrees. I also showed why 2,4 are false. If 1 is true then it's probably a standard fact, though curiously it's not mentioned on Wikipedia. This only leaves 3, which I'm sure will become immediate once you familiarize yourself with Turing degrees and their properties, say by reading a textbook. – Yuval Filmus Apr 10 '15 at 16:27
• Crossposted on math.se at math.stackexchange.com/questions/1228433/… . – Carl Mummert Apr 11 '15 at 17:41

To complete LogicLove's answer, the solution for (1) can be found in a math.se question.

As there are pairs of degrees which have no greatest lower bound, the conditions for a distributive lattice can't be met.

• +1. Luke I think half disjunctive lattice means upper semi lattice (join semmilattice) ? – nini Apr 11 '15 at 15:27
• @nini, maybe, I haven't heard of a half disjunctive lattice. – Luke Mathieson Apr 11 '15 at 15:46
• I think join means disjunctive? maybe ? – nini Apr 11 '15 at 16:32

(2) and (4) are false as explained by Yuval's Comment.

The lattice of Turing degrees has a minimum (the recursive degree) but no maximum, since the jump of any degree (i.e., the corresponding halting problem) is larger than the degree.

(3) is true, because the Turing Degrees form an upper semi-lattice.

I have no idea for (1).

• @Gilles you means upper semi lattice as half disjunctive lattice? Yes ? – nini Apr 11 '15 at 16:33