# Structure of partial recursive function over recursively enumerable guard

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.$$

• 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. – universalset Jan 17 '14 at 4:00
• Right, right. That was a mistake. Edited accordingly. – Biniam Jan 17 '14 at 15:12
• 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. – Biniam Jan 17 '14 at 15:27

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.