Does it matter for this function if the set we check membership of is finite?

I have the following problem.

Let $\Phi$ be an admissible numbering of the single-parameter partially-recursive functions. That is, $\Phi(i, x) = f_i(x)$ with $f_i$ the $i$th partially-recusive function with one parameter. Denote with $f(x)\!\uparrow$ that $f(x)$ is undefined in the sense that its computation does not halt.

Now let $B$ be a partially computable set (finite or infinite) so that $\Phi(i,i)\!\uparrow$ for all $i \in B$.

Show that

$\qquad H_1(x) = \begin{cases}1 \text{ if } \Phi(x,x)\downarrow \\ 0 \text{ if } x \in B \\ \uparrow \text{ otherwise}\end{cases}$

is partially recursive.

I know from here that there is even an infinite set. I am preparing for an exam, so just assume that they give an suitable infinite set. How would the program differ if B is a finite set like $B= \{b_1,b_2,\cdots,b_n\}$?

Also a function obtained from composition, recursion is partially computable. So since definition by piecewise is primitive recursive , Could I say $x \in B$ is partially computable if $B$ is finite or would it be better to comeup with a program. I don't know how using just these four instructions, one could say $x \in B$ or not.

\begin{array} \\ \;\;\;\;\;\;\;\;\;Y \gets 0 \\ \;\;\;\;\;\;\;\;\;\text{IF } X \neq 0 \text{ GOTO } A \\ [E] \;\;\;\text{ GOTO } E \\ [A]\;\;\;\; Y \gets Y+1 \end{array}

I am using the Davis book of Computability where this is mentioned in page 70 of second edition.

• I have trouble parsing your post. The original problem is rather easy if we can assume that $B$ is semi-decidable; you seem to think in too convoluted ways. What's the question you are having?
– Raphael
Oct 11 '16 at 6:24
• You seem to be asking whether for the purposes of the course, you can assume that every finite set is partially computable (without proving it explicitly). This is a question for your instructor. In a paper you can definitely assume that a finite set is partially computable, even computable. Oct 11 '16 at 20:23
• As a consequence of my preceding comment, it seems that this question can only be answered by your course instructor. Oct 11 '16 at 20:24
• 1) What "difference in writing a program" do you mean? Which "a program"? Note that finite sets are trivially decidable. 2) For showing that $H_1$ is semi-computable, we don't care if $B$ is finite. The conditions given in the problem statement are enough to work with. (One can ask if such $B$ exists at all, but that is beyond the scope of the problem.) 3) If you don't know the definition of semi-decidability (or partially recursiveness) you can not possible solve the problem. Read on and learn all the required definitions.
– Raphael
Oct 12 '16 at 8:27
• I tried to reorder your question so that the problem statement is clear. I still don't know what you are trying to do there; the problem is way more elementary than you seem to think. (cc @DavidRicherby)
– Raphael
Oct 12 '16 at 8:35

1 Answer

You can solve this problem in a straight-forward way: give an algorithm that (semi-)computes $H_1$.

Here is a rough sketch that you have to expand into appropriate detail in the model you want to work with and then show correctness and computability.

Let $M_B$ be a semi-decider for $B$.

1. Compute $\Phi(x,x)$ and $M_B(x)$ simultaneously.
2. If $\Phi(x,x)$ terminates first, return $1$.
3. If $M_B(x)$ terminates first (and accepts), return $0$.
4. Otherwise, loop.

Hints

• In step 1, use dovetailing.

• Steps 2 and 3 can not disagree.

• Step 4 only happens when it should.

You can show the necessary lemmas using the assumptions on $B$.

As you see, we don't care at all if $B$ is finite as we do not care what $M_B$ looks like; we just use it as a black box.

Aside: I am not sure that infinite $B$ with all the properties as listed in the question exist. We can ignore this, though: the problems is stated such that we show something for each such $B$ -- if there is none, we are good.