2
$\begingroup$

I have this question I'm struggling with.

Let $A=\{<i,n>|\;n \in \phi ^{(i)}\}$. In other words, $A$ is the language defined by the set of all pairs $<i,n>$ such that $n$ is $\leq_m$ to the $i$th Turing jump. A is definitely not an arithmetically definable language, and you can prove this by contradiction.

I have to find a language, let's say $B$, that is more complex than $A$ $i.e.$ $B\nleq_T A$. I thought about $B=\{<i,n>|\;n \not\in \phi ^{(i)}\}$, but I'm not sure about my reasoning, I think an oracle turing machine with an oracle $A$ couldn't reduce to $B$..

And one last thing, do you think there exists a language that is more complex than any other (it doesn't reduce to anything)?

If you have any hints that could help me solve those two questions I would be really grateful!

Improve this question
$\endgroup$
3
  • $\begingroup$ The proof of the undecidability of the halting problem relativizes, so given any language $A$, we can always find a language not reducible to $A$, which corresponds to the halting problem with an oracle to $A$. $\endgroup$
    – Yuval Filmus
    Commented Oct 21, 2013 at 1:13
  • $\begingroup$ I'm not trying to get a full answer, just a hint or two so i can know what to search for! Thanks a lot for your tips! $\endgroup$
    – Felix D.
    Commented Oct 21, 2013 at 3:20
  • $\begingroup$ I guess I was wrong because for any language $L$, $L\leq_T \overline{L}$... $\endgroup$
    – Felix D.
    Commented Oct 21, 2013 at 3:45

1 Answer 1

Reset to default
1
$\begingroup$

Reiterating my comment, for each $A$ we can construct a language $A'$ (read: $A$ jump) which cannot be reduced to $A$ by taking all halting TMs with oracle access to $A$. The classical proof of the undecidability of the halting problem applies, showing that $A'$ cannot be (Turing-)reduced to $A$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot! That's what i figured yesterday!! I was wondering at first if it was only applicable to arithmetic sets (members of arithmetic hierarchy). $\endgroup$
    – Felix D.
    Commented Oct 25, 2013 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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