0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Raphael Oct 11 '16 at 6:24
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 11 '16 at 20:23
  • $\begingroup$ As a consequence of my preceding comment, it seems that this question can only be answered by your course instructor. $\endgroup$ – Yuval Filmus Oct 11 '16 at 20:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Oct 12 '16 at 8:27
  • 2
    $\begingroup$ 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) $\endgroup$ – Raphael Oct 12 '16 at 8:35
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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