I am trying to follow the book on the proof that the factorial is a primitive recursive function and it is confusing as hell. It says(adsbygoogle = window.adsbygoogle || []).push({});

0!=1 y'!=y!y' (y' means the next one so 0=0 0'=1 0''=2 etc. )

We can simply define a two-argument function with a dummy argument, and then get rid of the dummy argument afterwards by composing with an identity function. For example in the case of the factorial function we can define

dummyfac(x,0)=const_1(x) (const_n(x)=n for all x)

dummyfac(x, y')=dummyfac(x,y)y'

so that dummyfac(x,y')=y! regardless the value of x, and then define fac(y)=dummyfac(y,y). More formally

fac=Cn[Pr[const_1, Cn[prod, id^3_3, id^3_2]], id, id]

The last part I do not understand at all. HOw the hell did they just come up with that function. Cn means take a composition of functions so Cn[f,g](x)=f(g(x)), Pr means primitive recursion functions, prod means product, id^a_b means if you have a list of a things, just take the bth one out of the list. It is just the identity.

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# What the hell is going on with this recursive function

Loading...

Similar Threads - hell going recursive | Date |
---|---|

I Recursive Ordinals and Creativity | Dec 14, 2017 |

B How do I go about calculating the expected profit/winning per play of this game | Nov 21, 2016 |

Reliability and MTTF, what's going on? | Dec 7, 2013 |

White noise going through a Hilbert filter. | Jun 22, 2013 |

Determining the right komi in the game of go (for 19x19 board) | May 12, 2013 |

**Physics Forums - The Fusion of Science and Community**