0
$\begingroup$

I need to classify the set $$\{p|∃y : \operatorname{Dom}(φ p ) ⊇ \operatorname{Dom}(φ y )\}$$ as decidable, semidecidable or not semidecidable.

I don't know how to start. Any ideas?

Dom (φp) it's all the inputs that are accepted by a turing machine "p", and the same for Dom (φy). So if My(some input) accepts then Mp(same input) accepts too, Mp can accept more inputs than My but not less.

But I don't know how work with that.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What are your ideas on the topic? $\endgroup$
    – Yuval Filmus
    Dec 4 '16 at 22:12
  • $\begingroup$ I have added my ideas on the question. $\endgroup$
    – Crider7
    Dec 5 '16 at 12:21
  • $\begingroup$ I am unfamiliar with your notation, but it seems that your set contains everything, since you cal always choose $y = p$. $\endgroup$
    – Yuval Filmus
    Dec 5 '16 at 12:23

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.