0
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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 ...
$\endgroup$
3
  • $\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$ Commented Apr 10, 2017 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$ Commented Apr 10, 2017 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$ Commented Apr 11, 2017 at 13:45

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.