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
