What the hell is going on with this recursive function

[gravenewworld]

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.

 

[mathwonk]

it is obvious that (n+1)! = n! (n+1). what else is there to know here?

someone is making a mountain out of a molehill.

 

[gravenewworld]

I know that, but I am trying to translaste that easy concept into the formal definition given. I have to be able to do it know with easy stuff before things start getting really rediculous.

 

[Hurkyl]

What is the formal definition?

 

[gnome]

Take a look at my thread "primitive recursive" started just a few days ago. Basically the same issue. Apparently recursion is formally defined in just those 2 ways & if you want to have a valid proof that a function was derived using recursion you have to do it in exactly one of those forms.

Have fun.

 

[gravenewworld]

fac=Cn[Pr[const_1, Cn[prod, id^3_3, id^3_2]], id, id] is the "formal definition" Just simply stating (n+1)(n+1)! shows that the factorial is PR, but it doesn't prove it. In order to prove it is PR, you have to be able to write it in the boxed form I gave. The requirement to show something is PR is to show that

h(x,0)=f(x), h(x,y')=g(x,y,h(x,y))

where f and g are the basic functions, or have been derived from basic functions. If something meets that criteria than the short hand way to write it is h=Pr[f,g]

 

[gravenewworld]

Gnome I am using Computability and Logic by George Boolos, Burgess, and Jeffrey. Does you text have a proof for the factorial function?

 

[Hurkyl]

Cn[f,p,q](x) = f(p(x), q(x))?


Clearly, you want this recurrence relation:

h(x, y') = y' * h(x, y)

Right?

So your goal is to create g(x, y, z) = y' * z.

Right?

So, all you need to do is construct * and ' out of basic functions, and compose them appropriately.

Rewriting: g(x, y, z) = Product(Successor(y), z)

...

 

[gravenewworld]

Cn[f,p,q](x) = f(p(x), q(x))
Clearly, you want this recurrence relation:

h(x, y') = y' * h(x, y)

Right?

So your goal is to create g(x, y, z) = y' * z.

Right?

So, all you need to do is construct * and ' out of basic functions, and compose them appropriately.

Rewriting: g(x, y, z) = Product(Successor(y), z)

so z is supposed to be fac(y) right? but then wouldn't I also have to make z come from basic functions as well, which is why the fac=Cn[Pr[const_1, Cn[prod, id^3_3, id^3_2]], id, id] looks so ugly? I'm sorry if I am not following, this is the first time I have ever done this, and I am studying this as an independent study.

 

[gravenewworld]

Cn by the way means composition of functions so, h(x1,...,xn)=f(g1(x1,...,xn),...,gm(x1,...,xn)) is just written as h=Cn[f,g1,..,gm] if f is a function of m arguments and each g1,...gm is a function of n arguments. So yes Cn[f,p,q](x)=f(p(x),q(x))

 

[Hurkyl]

so z is supposed to be fac(y) right?

Yes, and no. You want g to satisfy the equation:

g(x, y, y!) = y' y!

right? One solution is g(x, y, z) = y' z.



There isn't just one way to write the answer. I figured it would be more instructive to lead you to create your own answer than to slog through why this one is the right answer. (And who knows, maybe you'll derive the given answer!)


Do you see what's left to do after getting g(x, y, z) = Product(Successor(y), z)?

 

[gnome]

In case you're still interested in this, here's the way we proved factorial to be p.r.

I'm having a hard time visualizing your definitions; I don't know how much of that difficulty is due to the actual definition, and how much due to the lack of formatting.

Anyway, we used these definitions for recursion and composition:

recursion1:
$$h(0) = k$$
$$h(t+1) = g(t,h(t))$$

recursion2:
$$h(x_1,...,x_n,0) = f(x_1,...,x_n)$$
$$h(x_1,...,x_n,t+1) = g(t,h(x_1,...,x_n,t),(x_1,...,x_n))$$

composition1:
$$h(x) = f(g(x))$$

composition2:
$$h(x_1,...,x_n) = f(g_1(x_1,...,x_n),g_2(x_1,...,x_n),...,g_k(x_1,...,x_n))$$

and we took three "initial functions" (which are assumed to be p.r) to be:

successor:
$$s(x) = x + 1$$

null:
$$n(x) = 0$$

projection:
$$u_i^n (x_1,...,x_n) = x_i$$

This proof uses the simpler forms of recursion & composition.
It is also based on having already proven that
multiplication (*)
is primitive recursive.

The recursion equations for factorial are
0! = 1
(x+1)! = (x+1) * x!

To prove this to be p.r. we just show that this is exactly of the form
$$fact(0) = 1$$
$$fact(t+1) = g(t,fact(t))$$

as long as $g(x_1,x_2) = s(u_1^2(x_1,x_2)) * u_2^2(x_1,x_2)$, since we already know that * is primitive recursive.

 

[TenaliRaman]

and we took three "initial functions" (which are assumed to be p.r) to be:

The set PR of primitive recursive function is defined as follows :
1. All initial functions are elements of PR.
2. For any k>=0 and m>=0, if f:N^k -> N and
g1,g2,...,gk : N^k -> N are elements of PR. then the function
f(g1,g2,...,gk) obtained from f and g1,g2,..,gk by composition is an
element of PR.
3. For any n>=0, any function g : N^n+1 -> N in PR, and any function
h : N^n+2 -> N in PR, the function f : N^n+1 -> N obtained from g and h by primitive recursive is in PR.
4. No other functions are in the set PR.
(Source : John Martin)

-- AI

 

[gnome]

The set PR of primitive recursive function is defined as follows :
1. All initial functions are elements of PR.
2. For any k>=0 and m>=0, if f:N^k -> N and
g1,g2,...,gk : N^k -> N are elements of PR. then the function
f(g1,g2,...,gk) obtained from f and g1,g2,..,gk by composition is an
element of PR.
3. For any n>=0, any function g : N^n+1 -> N in PR, and any function
h : N^n+2 -> N in PR, the function f : N^n+1 -> N obtained from g and h by primitive recursive is in PR.
4. No other functions are in the set PR.
(Source : John Martin)

-- AI

Is there a point hidden in there someplace?

 

[TenaliRaman]

Yeap many.
There's a point after every serialised number and some points are included in the ellipsis.

Seriously,
the three functions you describe are the standard initial functions and they are defined as PR and not assumed as PR.

-- AI

 

[gnome]

So all that was just because you prefer "defined" to "assumed"? Definitions can differ.

And by the way, does John Martin really talk about the set of primitive recursive functions, or the class?

Actually, if you want to be picky we could say none of the above. They're just the three initial functions. They belong to every PRC class of functions, but they themselves are not necessarily primitive recursive functions. Martin Davis (who I think is more of an authority than John Martin) defines primitive recursive this way:

A function is called primitive recursive if it can be obtained from the initial functions by a finite number of applications of composition and recursion.

Anyway, what's the point of arguing about meaningless differences?

 

[TenaliRaman]

Firstly, calm down, if my last post was sounding offensive or harsh, i am sorry for that.
Secondly, my mention of the source, was just to show that the definition isn't picked out of the air and the source of definition is valid and accepted source.
Thirdly,
I was trying to point out that the mention of the sentence
"initial functions are assumed to be PR"
is wrong and should not be stated that way.

You can see that according to the definition i provided, initial functions are defined as PR's.

Now i will take your definition,
"A function is called primitive recursive if it can be obtained from the initial functions by a finite number of applications of composition and recursion."

I can express any of the initial functions in terms of the initial functions themselves by a finite number of applications of compositions and recursion. This automatically suggests that initial functions are PR's.

So in either case, the statement that initial functions are assumed to be PR's is wrong.

Anyway, what's the point of arguing about meaningless differences?

If this were a computer program, and if i were arguing using properly named variables instead some random alphabets as variables, i would probably agree with you here. But this is theoretical computer science so sometimes things get sticky if they are not properly defined.

I repeat , the attempt here is to correct an error and not to show someone down or to prove that the book i follow is superior than the book u follow or any such anti-constructive thought.

-- AI

 

[gravenewworld]

Alright thanks guys for all the help. I finally was able to get through this chapter after tons of work. I'm sure the next chapter on recursive sets and relations is going to be even more fun