1
$\begingroup$

I don't think so, because $A_{TM} = \{<M,w>\mid \text{M accepts w}\}$ is not Turing-decidable. Is this the right way to think about?

$\endgroup$
2
$\begingroup$

No. If there exists such a language, say $\Omega$, then for any language, there exists a TM $M_L$ with the ability to query to $\Omega$ that recognizes $L$, and obviously the mapping from $L$ to $M_L$ is an injection. However, the set of languages are uncountable while the set of TMs are countable, which leads to a contradiction.

$\endgroup$
2
$\begingroup$

I assume you're asking if there's a language $\Omega$ such that, for all $L\subseteq\{0,1\}^*$, $L\leq_T\Omega$. In that case, the answer is “no.”

For any language $\Omega$, the languages that Turing-reduce to $\Omega$ are those that can be decided by a Turing machine with an oracle for $\Omega$. For brevity, I'll say “$\Omega$-Turing machines” instead of “Turing machines with an oracle for $\Omega$.” $\Omega$-Turing machines are at least as powerful as ordinary Turing machines (exactly as powerful, if $\Omega$ is decidable; strictly more powerful of it isn't).

The same argument that shows the undecidability of the ordinary Turing machine halting problem also shows that any machine model that is at least as powerful as Turing machines can't decide its own halting problem. So, in particular, no $\Omega$-Turing machine can decide the halting problem for $\Omega$-Turing machines. In other words, for any language $\Omega$, the halting problem for $\Omega$-Turing machines isn't Turing-reducible to $\Omega$.

This means that there's no “hardest language” (or class of languages) to which all languages are Turing-reducible. This is related to the concept of Turing degrees, which form an infinite hierarchy of ever more difficult languages: start with the decidable languages, then the languages decided by Turing machines with an oracle for the halting problem, and then iterate by making each subsequent level be the languages decided by Turing machines with an oracle for the halting problem corresponding to the previous level.

$\endgroup$
  • $\begingroup$ so I can just show halting problem still leads to a contradiction to prove there does not exist such a language $\Omega$? $\endgroup$ – Anonny Apr 11 '18 at 17:53
  • $\begingroup$ @Anonny No, you need to use specific variants of the halting problem. For example, if you take $\Omega$ to be the halting language for ordinary Turing machines ("the halting problem"), then obviously $\Omega$ is reducible to itself -- all languages are. $\endgroup$ – David Richerby Apr 11 '18 at 19:09

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.