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.

| cite | improve this question | | | | |
$\endgroup$
  • 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.