- #1
gravenewworld
- 1,132
- 26
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
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.
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.