Classify as decidable, semi-decidable or not semi-decidable

346 Views Asked by At

I have the set {p|∃y : Dom(ϕp) ⊆ Dom(ϕy)} and have to classify it as decidable, semi-decidable or not semi-decidable. I made a research and I found:

Semi-Decidable

If I have a word w ∈ L then a p program with input w stops and return "accept"

If I have a word w ∈/ L then a p program with input w don't stop or don't accept.

Decidable

If I have a word w ∈ L then a p program with input w stops and return "accept"

If I have a word w ∈/ L then a p program with input w stops and don't return "accept"

I didn't understand the relation between "classify" and my set, so I don't know how to classify it. I will preciate an explanation if possible.

1

There are 1 best solutions below

0
On

Then a good explanation will be: It is decidable because I always can choose p = y and then all turing machines will accept for this set, because a TM y can take input of the TM p and accepts so the words that this set accepts will be Σ*.