# prove that $h(x)$ is partial recursive

If $f:A^*\rightarrow A*$ and $g:A^* \rightarrow A^*$ are partial recursive we want to prove $h:A^* \rightarrow A^*$ with the following definition is partial recursive $$h(x) = \begin{cases} \lambda & f(x) = \lambda\\ g(x) & \textrm{otherwise} \end{cases}$$ for $x \in Dom(f)$.

One of my friends tried using a $\textrm{step}$ function that we know is primitive recursive and also partial recursive $$\textrm{step}(x,y) = \begin{cases} C_{\lambda} & x = \lambda\\ y & \textrm{otherwise} \end{cases}$$ and defined $h(x) = \textrm{step}(f(x),g(x))$. but I think there is a problem here because we are not using the fact that $f$ and $g$ are partial recursive. Is this solution correct or not?

• Minor point: is the notation "for $x\in Dom(f)$" meant to imply that $h(x)$ is undefined elsewhere?
– chi
Commented Jan 19, 2018 at 20:37

I think there is a problem here because we are not using the fact that $f$ and $g$ are partial recursive.
Yes, you are, or at least you should be. Consider $h'(x) = \textrm{step}(f(x), \Omega(x))$ where $\Omega$ is not partial recursive. Would you consider that to be partial recursive? If not, why not?
If you define $h(x)$ as your friend has, you need to prove firstly that it's equivalent to the original definition. Once you've done that, it suffices to prove that it's partial recursive. But composition of p.r. functions gives a p.r. function, which is the key step that either your friend forgot to state or that you have overlooked.