Having trouble with showing that function is primitive recursive. Have the following problem.

Let $ f: \mathbb{N} \rightarrow \mathbb{N}$ be decreasing function. Show that $f$ is primitive recursive.

I see that $f$ will eventually decrease to a certain constant and that I could say that it is a constant function with over certain numbers which would make it primitive recursive. I don't think this is enough, however, and that I need something more.


Why isn't that enough? An algorithm to calculate it could be of the form

if n = 1 then return ...
else if n = 2 then return ...
else ...
else return ...
  • $\begingroup$ Because the function isn't a constant function and it turns into one eventually. I think I am just misunderstanding some part of this but I don't think this would be a proper proof. $\endgroup$ – E.K. Apr 10 '17 at 16:19
  • $\begingroup$ There are various characterizations of primitive recursive functions. One is: a function that can be computed using an algorithm that contains a limited set of instructions: constants, the successor function, equals, if-then-else, and bounded loops. $\endgroup$ – Robert Israel Apr 10 '17 at 19:46
  • $\begingroup$ So because I know that the function will turn into a constant at a certain point $n$ that is less than infinity I can say that the function will limited number of intructions which is pretty much the definition of primitive recursion. I think I got it now. $\endgroup$ – E.K. Apr 11 '17 at 13:45

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.