I've been trying to figure out a practice exam question, about if a given $P$.

$P$ is the characteristics of recursive enumerable set given as:

$$P(A) = \begin{cases} ⊤ &if &|A| ≤ 100 \\ ⊥ & else. \end{cases}$$

Now I know string properties state:

  1. Decidable if $ \{ x$ $|$$ $ $ P(x) \} $ is recursive
  2. Semi-decidable if $ \{ x$ $|$$ $ $ P(x) \} $ is recursive enumerable
  3. Undecidable if $ \{ x$ $|$$ $ $ P(x) \} $ is not recursive

How do I apply this and triviality, and monotonic properties to $P$ to see if it's undecidable. Or if you have another way, please share!

My first thought was that it's semi-decidable because it's r.e. but how do I prove it's not decidable? From the given statement, how can I tell if it's using recursion or not?

  • $\begingroup$ What have you tried? What strategies do you know for proving something is not decidable? Have you tried any of them, and if so, what progress did you make and what happened? We're more interested in helping you understand concepts than in doing your practice question for you, but that requires you to show your current understanding and exhaust all approaches you know and show us what happened when you tried them; as it stands you haven't given us a lot to work with. $\endgroup$ – D.W. Jun 28 '16 at 0:29
  • $\begingroup$ @D.W. I have the answer, which says: P is not decidable, because it's not trivial (with an example proof). The it says P is not monotonic, with another proof. However I'm simply asking someone to walk me through the logic of how to get there. This isn't me asking someone to make my homework, I just don't understand how one can derive this from stack symbols. I don't want to come over as rude, but I just really don't get it. I can bash my head around and write down every approach I get but it won't lead me to the answer, hence me coming here for help. [not trying to be rude] $\endgroup$ – marcusvb Jun 28 '16 at 1:31
  • $\begingroup$ According to your definitions every semi-decidable set is also undecidable, because recursive enumerable sets are not recursive. I would say to use "not recursive enumerable" in 3. $\endgroup$ – Bakuriu Jun 28 '16 at 10:47

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.