[Solved]: Decidability of the language that accepts a universal turing machine

Problem Detail: 

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?

Asked By : mercurial

Answered By : newbie

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18506

 Ask a Question

 Download Related Notes/Documents