If we have a function $g\colon \mathbb{N}^{k+1} \to \mathbb{N}$ which is primitive-recursive. How to show that the function $f\colon \mathbb{N}^{k+1} \to \mathbb{N}$ with

$$f(x_1, \dots, x_k , x_{k+1})= \sum_{i=0}^{x_{k+1}}g(x_1,\dots, x_k,i)$$

is also primitive recursive?

  • 4
    $\begingroup$ You show how to implement it using the operations allowed in primitive recursion. Think of it as a kind of programming exercise. $\endgroup$ – David Richerby Jun 14 '16 at 21:02
  • $\begingroup$ So wouldn't it be possible to show it with some kind of induction? $\endgroup$ – fragant Jun 14 '16 at 21:04
  • 1
    $\begingroup$ Induction on what? $\endgroup$ – David Richerby Jun 14 '16 at 21:05
  • $\begingroup$ So we have a primitve recursive function $f$ and the composition and additon of primitive recursive function is also primitive recursive and with these operations would it be possible to define the rhs inductive? $\endgroup$ – fragant Jun 14 '16 at 21:08
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Aug 14 '16 at 22:47

Primitive recursive means the function can be calculated using loops where the number of iterations is calculated ahead before running the loop.

So how often would you run the loop to calculate the sum?

| cite | improve this answer | |
  • 2
    $\begingroup$ This does not seem to constitute an answer. Plus, the criterion "is calculated ahead before running the loop" seems to be rather imprecise; calculated how? $\endgroup$ – Raphael Jul 16 '16 at 16:31
  • $\begingroup$ Well, using primitive recursion, of course :-) $\endgroup$ – Andrej Bauer Aug 15 '16 at 1:23

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.