I am given a Turing machine M as input and i have to find out if this language below decidable and if not is it then in this case recursively enumerable .

$$L=\\\{<M> \mid \text{ is there $w_1,w_2$ for M so that M for both halts but with different results }\}$$

Somehow i ended up finding that the language is not decidable nor R.E .

if you have an other point of view , can you then please give me some hints.

  • $\begingroup$ How is "...$M$ for both halts but with different results" interpreted? Is it "If $M(w_1)$ and $M(w_2)$ halt then $M(w_1) \neq M(w_2)$" or "$M(w_1)$ halts AND $M(w_2)$ halts AND $M(w_1) \neq M(w_2)$"? $\endgroup$ – fade2black Dec 15 '17 at 18:29
  • $\begingroup$ like for example after halting ,$w_1$ ist accepted and $w_2$ is not $\endgroup$ – Mohbenay Dec 15 '17 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.