1. Apr 12, 2005

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?

2. Apr 12, 2005

Hurkyl

Staff Emeritus
$$\chi (n) := \left\{ \begin{array}{ll} 1 \quad & \forall m < n: f(m) \neq f(n) \\ 0 & \exists m < n: f(m) = f(n) \end{array}$$

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.