1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Are you familiar with Rice's theorem? $\endgroup$ – Shaull Dec 1 '13 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$ – David Richerby Dec 2 '13 at 9:06
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ "$\{w\mid w_i\notin M_i\}$". Neither $w_i$ nor $M_i$ is defined. What are they? $\endgroup$ – David Richerby Dec 2 '13 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 Dec 2 '13 at 11:14

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.