Is the language $L_{universal} = \{ \left \langle M \right \rangle | M \textrm{is a universal turing machine} \}$ decidable?

I'm guessing it is decidable according to the definition of a UTM, that a UTM must be able to calculate every recursive function. Since the set of recursive languages and the set of all input words are both enumerable, we are theoretically able to determine if the given $\left \langle M \right \rangle$ is a UTM. Is my logic somewhat correct?

  • 4
    $\begingroup$ Are you familiar with Rice's theorem? $\endgroup$
    – Shaull
    Commented Dec 1, 2013 at 18:30
  • $\begingroup$ If you think it's decidable, you must think you have some algorithm that, in particular, can tell the difference between a real Turing machine and one that gives the wrong answer for a couple of inputs. How do you think you are doing that? $\endgroup$ Commented Dec 2, 2013 at 9:06

2 Answers 2


If $L_{u}$ would be decidable, $L_u^\complement$ would be decidable too (the complement of a recursive language is recursive too) , but if you can build a TM that accepts $L_u^\complement$ you can build a TM that accepts $L_d=\{w \mid w_i \notin L(M_i)\} $ that is not RE.

In fact if $w \in L_d \implies (w,w)\notin L_u \implies (w,w) \in L_u^\complement$.

So with a reduction from $L_d$ to $L_u$ it can be shown that $L_u$ is not decidable.

  • $\begingroup$ "$\{w\mid w_i\notin M_i\}$". Neither $w_i$ nor $M_i$ is defined. What are they? $\endgroup$ Commented Dec 2, 2013 at 10:53
  • $\begingroup$ the $i^{th}$ string and the $i^{th}$ TM, I mean $L_d$ the set of string such that the TM with code $w$ doesn't accept when it receives the string w as input. There was a mistake, I wrote $M_i$ instead of $L(M_i)$ $\endgroup$
    – abc
    Commented Dec 2, 2013 at 11:14

Rice's theorem: Every nontrivial property of the RE languages is undecidable.

you are asking about machines M' that recognize the same language as $L_{\mathcal{u}}$:

$$ \{ \langle M' \rangle : L(M') = L_{\mathcal{u}} \} $$

a non-trivial property (A property is trivial if is either empty (i.e., satisfied by no language at all), or is all RE languages. Otherwise, it is nontrivial).

is $L_{universal}$ the same language as $L_{\mathcal{u}}$?


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.