3
$\begingroup$

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: enter image description here

$\endgroup$
6
  • 3
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Apr 10, 2015 at 11:45
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 10, 2015 at 16:22
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 10, 2015 at 16:27
  • 1
    $\begingroup$ Crossposted on math.se at math.stackexchange.com/questions/1228433/… . $\endgroup$ Apr 11, 2015 at 17:41
  • $\begingroup$ this site does not seem to have much on turing degrees which is a part of the theory, here maybe is the closest available question, "reductions among undecidable problems". $\endgroup$
    – vzn
    Apr 11, 2015 at 23:52

2 Answers 2

5
$\begingroup$

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.

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

(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).

$\endgroup$
1
  • $\begingroup$ @Gilles you means upper semi lattice as half disjunctive lattice? Yes ? $\endgroup$
    – nini
    Apr 11, 2015 at 16:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.