4
$\begingroup$

How can I solve the following problem:

Let $f, \pi, g$ accept one, two and three arguments respectively. If you know that $f, \pi, g$ are primitive recursive functions prove that $h$ defined as: $$ \begin{align*} h(0, y) &\simeq f(y) \\ h(x + 1, y) &\simeq g(x, y, h(x, \pi(x, y))) \end{align*} $$ is also primitive recursive function.

The definition of primitive recursion I know is: $$ \begin{align*} h(\bar{x}, 0) &\simeq f(\bar{x}) \\ h(\bar{x}, y + 1) &\simeq g(\bar{x}, y, h(\bar{x}, y)) \end{align*} $$

  • 0
    Identical problem posted to MO, http://mathoverflow.net/questions/81757/how-to-prove-that-this-function-is-primitive-recursive-closed I recommend reading what's posted there before answering here.2011-11-27
  • 0
    This question might have been perfect for the upcoming [Computer Science Stack Exchange](http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=pdx8p7tVWqozXN85c5ibxQ2). So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off!2011-12-03

2 Answers 2