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!

  • $\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 Oct 21 '13 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. Oct 21 '13 at 3:20
  • $\begingroup$ I guess I was wrong because for any language $L$, $L\leq_T \overline{L}$... $\endgroup$ – Felix D. Oct 21 '13 at 3:45

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$.

  • $\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. Oct 25 '13 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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