Hint: There are several ways to show that this function is primitive recursive. Here are two possibilities:
Note: The PLUS function was defined in class for only 2 arguments. If for your solutions for this part you need a more general PLUS_{k}(n_{1},n_{2},...,n_{k}) function, make sure to define it and to prove that it is primitive recursive.
For each one of them:
For instance, if you need to use a constant, say 2, different from 0, then you will express it as succ(succ(0)).
Submit a file with your code and a transcript showing the output produced by your implementation on the following set of inputs:
Hint: See the code provided for the solutions of HW2 in D-term 2002, and the code provided for the solutions of HW2 in B-term 2002.
Hints: Here are a couple of comments on this:
- Note that there is a formula to solve the quadratic equation c_{0} + c_{1}*x - c_{2}*x^{2} = 0, or equivalently -c_{0} -c_{1}*x + c_{2}*x^{2} = 0. The formula is:
root(c_{0},c_{1},c_{2}) = "[1/(2*c_{2})]*[c_{1} +- sqrt((c_{1}*c_{1}) + 4*c_{0}*c_{2})]" If you apply that formula, two solutions can be obtained. HOWEVER, those solutions are not guaranteed to be integer numbers (not even real numbers as they may be complex numbers containing an imaginary part).- Hence, the suggested procedure is to:
- use mu-minimization, checking if 0 is a root; if not trying 1; if not, trying 2; etc.
- show that this minimization is "bounded" that is, that there is an upper bound for the number that needs to be tried. In other words, that the procedure above (trying 0, 1, 2, ...) doesn't need to go for ever, and that there is a number, say u, such that it is enough to try 0, 1, 2, ...., u and if none of those numbers are roots of the equation, then there are no integer roots for the equation.
You should compute that upper bound explicitly in terms of c_{0}, c_{1}, and c_{2}. For inspiration on how to do so, see problem 3.18 on p.149 of your textbook.