I read that the function $$ f(n) = \left\{ \begin{array}{l l} g(n) & \quad \text{if $n \in A$}\\ \text{undefined} & \quad \text{otherwise} \end{array} \right. $$

is recursive if $g(n)$ is recursive and the guard $if$ $n \in A$ is recursively enumerable (since the always $\text{undefined}$ function is recursive).

I read also that if the $else$ part is not always $undefined$, we cannot conclude that $f$ is not recursive.

Could anyone please explain why we should use the always undefined function in the else part when we have an r.e. guard? And also if $f$ was defined as follows, what conditions should $h(n)$ fulfil (apart from being always undefined) so that $f$ is recursive.

$$ f(n) = \left\{ \begin{array}{l l} g(n) & \quad \text{if $n \in A$}\\ h(n) & \quad \text{otherwise} \end{array} \right. $$

  • $\begingroup$ I'm almost certain that you want to have $g(n)$ (and $h(n)$), not $g(x)$, here, since as written $x$ is neither an input to your function nor is it defined anywhere. You also seem to have an extraneous "not" near the end of your second sentence. $\endgroup$ – universalset Jan 17 '14 at 4:00
  • $\begingroup$ Right, right. That was a mistake. Edited accordingly. $\endgroup$ – Biniam Jan 17 '14 at 15:12
  • $\begingroup$ About this sentence: "I read also that if the else part is not always undefined, we cannot conclude that f is not recursive.", the idea was if $f$ was defined as the first one, and if $A$ is recursively enumerable then we are guaranteed that $f$ is recursive. But if we instead used the second definition of $f$, we cannot say $f$ is NOT recursive without looking into $h$. As per your explanation, now it makes sense. $\endgroup$ – Biniam Jan 17 '14 at 15:27

There seem to be a few confusions implicit in your question, so let me try to explain what is going on here before addressing your explicit questions.

Let's consider what happens for a function $f$ defined as in your first expression. One proves the function $f$ is recursive by showing how to compute it, in the following way: On input $n$, begin enumerating $A$ (which can be done recursively because $A$ is recursively enumerable). If ever $n$ appears in the enumeration, then we know that $n \in A$: in that case, compute and output $g(n)$ (a recursive function). Since $n$ will eventually be enumerated if and only if $n\in A$, this means that our procedure outputs $g(n)$ exactly when $n\in A$, and our procedure never halts exactly when $n\not\in A$. Thus this procedure in fact computes $f(n)$, so $f$ is a (partial) recursive function.

Note that this construction doesn't work, and thus we can't conclude that $f$ is recursive, if we need our program to output something when $n\not\in A$. If $A$ is not recursive (but only recursively enumerable), we can never be satisfied, no matter how much of $A$ we enumerate, that some $n\not\in A$. So we won't be able to rely on an enumeration of $A$ to decide what to output depending on whether $n\in A$, because if we ever chose to guess that $n\not\in A$ (having not seen it so far) we could potentially be wrong. This is why we need $f$ to be undefined for $n\not\in A$ if we are to conclude that $f$ is recursive.

Lastly, you ask what are the conditions for $h$ under which a function $f$, which is defined to be $f(n)=g(n)$ for $n\in A$ and $f(n)=h(n)$ otherwise, is recursive. It's not really possible to give a general answer to this that doesn't just restate the problem. Certainly some sure $h$ work: for instance, $h=g$ (because then $f = g$ as well, and thus $f$ is recursive because $g$ is). In general there could be many such $h$, because there are many recursive functions which coincide with $g$ for values in $A$. Describing all such functions is essentially impossible. What you cannot do (at least if $A$ is not recursive itself) is find such a function $h$ such that $g(n)\neq h(n)$ for all (or all but finitely many) $n$. If you could, then you could determine (by computing $f(n)$, $g(n)$, and $h(n)$) whether or not $n\in A$, and hence $A$ would be recursive.


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.