0

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.

E.K.
  • 99

1 Answers1

1

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 ...
Robert Israel
  • 448,999
  • 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. – E.K. Apr 10 '17 at 16:19
  • 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. – Robert Israel Apr 10 '17 at 19:46
  • 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. – E.K. Apr 11 '17 at 13:45