2
$\begingroup$

In order to prove a certain function to be partially computable, I need to show an $\mathbb S$-program that computes it. I could really use the predicate $X \in B$ in my program to draw my conclusion. To give you the idea of what I am dealing with here it is one of my problems:

Give an infinite set $B$ such that $\Phi(x,x)\uparrow$ for all $b \in B$ and such that $$H(x) = \begin{cases}1 \text{ if } \Phi(x,x)\downarrow \\ 0 \text{ if } x \in B \\ \uparrow \text{ otherwise}\end{cases}$$ show that $H(x)$ is partially computable.

I am wondering if membership for infinite set is decidable and therefore can be used to write $\text{IF } X \in B$ such program. Am I allowed?

Edit: the notation $\Phi(x,x)\uparrow$ means the function is undefined.

Improve this question
$\endgroup$
8
  • 4
    $\begingroup$ It depends on the set. It is decidable whether a number belongs to the set of all primer. It is not decidable whether a number is the code of a total function. You should explain more carefully what your exact problem is. Also, the rest of the planet does not necessarily know what a "$\mathbb{S}$-program" might be (but we can also tell it doesn't matter). $\endgroup$
    – Andrej Bauer
    Nov 21, 2013 at 21:04
  • $\begingroup$ Is the beginning of the second paragraph supposed to be "$B$ such that $\Phi(x,x)\uparrow$ for all $x \in B$"? $\endgroup$
    – Andrej Bauer
    Nov 21, 2013 at 21:04
  • 3
    $\begingroup$ I am going to go in a limb here and guess that your set $B$ is assumed to be recursively enumerable. Then the whole thing becomes a homework, more or less. $\endgroup$
    – Andrej Bauer
    Nov 21, 2013 at 21:05
  • $\begingroup$ Some infinite sets can be searched in finite time see here $\endgroup$
    – adrianN
    Nov 22, 2013 at 9:47
  • 1
    $\begingroup$ @adrianN I can't tell whether I should be honored, amused, or disappointed that you're referring to my own blog (but a post written by a guest contributer). $\endgroup$
    – Andrej Bauer
    Nov 22, 2013 at 22:01

1 Answer 1

Reset to default
1
$\begingroup$

No, this is not allowed, in general, if we know nothing about the set $B$.

As Andrej Bauer explains in the comments: if the set $B$ is arbitrary and there are no guarantees about the set $B$ (as you state in the comments), then no, you cannot write "IF $X \in B$" in a program, as the predicate $X \in B$ might not be computable (depending upon the set $B$).

Re-reading your question, I see that you are allowed to choose a set $B$ of your choice (subject to some conditions). If you're able to choose $B$ in a way that makes $B$ recursively enumerable, then $B$ is no longer completely arbitrary and you now have an additional condition on $B$ which makes this a straightforward homework (as Andrej Bauer also explains in the comments).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.