$f(x,y)= 0$ if $x>y$ and $1$ otherwise.

How can prove formally that this function is primitive recursive?

  • 2
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. You may also want to check out our reference questions. $\endgroup$ – David Richerby Jun 2 '15 at 9:02
  • $\begingroup$ By the way, primates are the class of animals including monkeys and people. I've edited. :-) $\endgroup$ – David Richerby Jun 2 '15 at 10:31
  • 1
    $\begingroup$ @DavidRicherby Too bad you edited, I was going to suggest the banana test to do the proof. - - - - - - - @ adel : maybe you should look at the definition of primitive recursive and see how that function could fit. $\endgroup$ – babou Jun 2 '15 at 12:58
  • 1
    $\begingroup$ There is no point in downvoting. Depending on how much was done in class, this may be far from easy to a beginner. He should have shown what he tried. ==> @ adel have you learned to define some functions in class? Look how it is done. Possibly you can reuse some of them to go further, such as following the hint given in the first answer. $\endgroup$ – babou Jun 2 '15 at 15:21

Hint: One possible approach is to compose the functions $x\dot{-}y = \max(x-y,0)$ and $\delta(z) = \begin{cases} 0 & z=0, \\ 1 & z>0 \end{cases}$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.