0
$\begingroup$

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?

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

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.

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