Combination of Recursive Functions
Until this has been finished, please leave {{refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
Theorem
Let $f: \N^k \to \N$ and $g: \N^k \to \N$ be recursive functions (not necessarily total), where $k \ge 1$.
Let $\mathcal R$ be a $k$-ary relation such that:
- if $\mathcal R \left({n_1, n_2, \ldots, n_k}\right)$ holds, then $f \left({n_1, n_2, \ldots, n_k}\right)$ is defined
- if $\mathcal R \left({n_1, n_2, \ldots, n_k}\right)$ does not hold, then $g \left({n_1, n_2, \ldots, n_k}\right)$ is defined.
Let $h: \N^k \to \N$ be the function defined as:
- $h \left({n_1, n_2, \ldots, n_k}\right) = \begin{cases} f \left({n_1, n_2, \ldots, n_k}\right) & : \text{if } \mathcal R \left({n_1, n_2, \ldots, n_k}\right) \text { holds} \\ g \left({n_1, n_2, \ldots, n_k}\right) & : \text{otherwise} \end{cases}$
so that $h$ is total.
Then $h$ is recursive.
Proof
Let $P_f, P_g, P_\mathcal R$ be the URM programs computing, respectively, the functions $f$ and $g$ and the characteristic function $\chi_\mathcal R$.
From Recursive Function is URM Computable, these programs are guaranteed to exist.
An informal algorithm for computing $h$ is as follows.
- Input $\left({n_1, n_2, \ldots, n_k}\right)$.
- Use $P_\mathcal R$ to determine whether $\mathcal R \left({n_1, n_2, \ldots, n_k}\right)$ holds.
- If it holds, use $P_f$ to compute $f \left({n_1, n_2, \ldots, n_k}\right)$.
- If it does not hold, use $P_g$ to compute $g \left({n_1, n_2, \ldots, n_k}\right)$.
The result follows from URM Computable Function is Recursive.
$\blacksquare$
Fallacious Proof
We might attempt to show that $h$ is recursive by using the equation:
| \(\displaystyle h \left({n_1, n_2, \ldots, n_k}\right)\) | \(=\) | \(\displaystyle f \left({n_1, n_2, \ldots, n_k}\right) \chi_\mathcal R \left({n_1, n_2, \ldots, n_k}\right)\) | |||||||||||
| \(\displaystyle \) | \(+\) | \(\displaystyle g \left({n_1, n_2, \ldots, n_k}\right) \overline{\operatorname{sgn} } \left({\chi_\mathcal R \left({n_1, n_2, \ldots, n_k}\right)}\right)\) |
where $\overline{\operatorname{sgn}}$ is the signum bar function, known to be primitive recursive.
Then the right hand side is obtained by substitution from known recursive functions, so is recursive, and hence $h$ is recursive.
However, this fails as follows.
Although $h \left({n_1, n_2, \ldots, n_k}\right)$ is always defined,
| \(\text {(1)}: \quad\) | \(\displaystyle \) | \(\) | \(\displaystyle f \left({n_1, n_2, \ldots, n_k}\right) \chi_\mathcal R \left({n_1, n_2, \ldots, n_k}\right)\) | ||||||||||
| \(\displaystyle \) | \(+\) | \(\displaystyle g \left({n_1, n_2, \ldots, n_k}\right) \overline{\operatorname{sgn} } \left({\chi_\mathcal R \left({n_1, n_2, \ldots, n_k}\right)}\right)\) |
might not be.
$f$ and $g$ might not be total, in which case there may be some $\left({n_1, n_2, \ldots, n_k}\right)$ for which at least one of $f \left({n_1, n_2, \ldots, n_k}\right)$ and $g \left({n_1, n_2, \ldots, n_k}\right)$ is not defined.
This means $(1)$ is not defined for those values of $\left({n_1, n_2, \ldots, n_k}\right)$.
Note that $(1)$ does define a recursive function, but its domain consists only of those $\left({n_1, n_2, \ldots, n_k}\right)$ for which $f \left({n_1, n_2, \ldots, n_k}\right)$ and $g \left({n_1, n_2, \ldots, n_k}\right)$ are both defined.
Thus we establish the result by means of the indirect approach requiring the use of the results concerning the equivalence of recursive functions and URM computable functions.
