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

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    [tex]
    \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}
    [/tex]

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Primitive recursive functions :mad:
  1. Primitive recursive (Replies: 1)

  2. Transfinite recursion (Replies: 5)

Loading...