Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
For the undecidable languages I have seen so far , I am able to give a reduction from one language to other . Is it the case that every undecidable language is reducible to every other undecidable language?
If not can you prove that there exists 2 undecidable languages A and B such that A is not reducible to B.
Note : I am not talking only about mappping reducibility . I am talking about reducibility in general .
There is no concept of "reducibility in general". You always have to specify the power of the reduction. For example, if you allow mapping reductions but with literally any function (not necessarily a computable function) performing the mapping, then any language is reducible to any non-trivial language (i.e., anything other than $\emptyset$ or $\Sigma^*$).
If you do limit the power of the reduction in any way, then there are always pairs of problems $X$ and $Y$ such that $X\not\leq Y$. For example, take any language $X$ that isn't decidable in whatever model of computation you're using to define your reductions. Under that model of reductions, $X\not\leq \{0\}$.
OK, but you asked about undecidable languages and $\{0\}$ isn't undecidable. So, let $H_0$ be the halting problem for the model of computation you're using for your reductions. Let $H_1$ be the halting problem for Turing machines that have an oracle for $H_0$ (if $H_0$ is decidable, this is just the ordinary Turing machine halting problem), and let $H_2$ be the halting problem for Turing machines that have an oracle for $H_1$. Essentially the same proof that the ordinary Turing machine halting problem is undecidable shows that $H_2\not\leq H_1$, and both of these languages are undecidable.
Actually, I don't think that last paragraph is quite right. In the case that your model of reductions is more powerful than Turing machines, you probably need to use the reduction model instead of Turing machines to define the pair of halting problems. I don't have time to fix this right now but I'll come back to it this evening (UK time).
You are probably thinking about undecidable languages which are computably enumerable. Otherwise, the diagonalization technique described in answers to similar questions would have provided simple counterexamples. If you don't care about the computably enumerable part, then I would say that your question is simply a duplicate of one of the similar questions.
The halting problem is at least as strong than any such language, because you can just fix the string for which you want to know whether it is in the language, define a Turing machine which enumerates the strings in the language until it finds the given string and then stops, and then ask the halting oracle whether that Turing machine will stop.
So are there such languages which are weaker than the halting problem and still undecidable? Yes, there are (at least ZFC claims that there are, and most other reasonable formal systems will think so too). Can I write down such a language? No, not at the moment. Does anybody knows how to write down such a language? Maybe, I don't know.
Why do I write an answer, if I can't really provide an explicit answer? Because I want to point out a connection to formal systems. A language strong enough to complement a given axiom system (able to talk about TM like Peano arithmetic (PA) for example) to a consistent set of axioms complete for $\Pi^0_1$ sentences (i.e. the halting problem) provides enough computational power to construct a model of the given axiom system, and the set of $\Pi^0_1$ sentences of any model gives such language. The following answer by Noah Schweber first defines what it means to complement PA (as an example)
A set $A$ of (indices for) $\Pi^0_1$ sentences is plausible if $PA\cup A\cup\{\neg \varphi: \varphi\in\Pi^0_1\setminus A\}$ is consistent.
And then proceeds to show how Rosser's trick can be used to show
I claim that every plausible set $A$ is of PA degree
i.e. construct a model of the given axiom system (PA in this case). And if you had a stronger axiom system like ZFC, then being plausible with respect to ZFC would define you a ZFC degree, which is at least as strong as the PA degree. (I guess there are languages of PA degree which are not of ZFC degree, but in this case I don't even know whether ZFC claims this.)
