Primitive recursive functions :mad:

[novawildcat]

Let f be a primitive recursive total function, and let A be the set of all n such that the value f(n) is 'new' in the sense of being different from f(m) for all m<n. Show that A is primitive recursive.


How in the world do I attack this problem? I am totally lost. Any help would be greatly appreciated. Thanks.


I know that to show a set is primitive recursive the characteristic function of the set must be primitive recursive. What in the world, however, would be a suitable characteristic function for this set described above?

 

[Hurkyl]

What in the world, however, would be a suitable characteristic function for this set described above?

<br /> \chi (n) := \left\{<br /> \begin{array}{ll}<br /> 1 \quad &amp; \forall m &lt; n: f(m) \neq f(n) \\<br /> 0 &amp; \exists m &lt; n: f(m) = f(n)<br /> \end{array}<br />

Sounds good, I think.

I think the better question to ask, though, is an algorithm for actually computing &chi;(n)... it doesn't even have to be a good algorithm, just an algorithm.