Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Primitive recursive functions :mad:

  1. Apr 12, 2005 #1
    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. jcsd
  3. Apr 12, 2005 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    \chi (n) := \left\{
    1 \quad & \forall m < n: f(m) \neq f(n) \\
    0 & \exists m < n: f(m) = f(n)

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook