What makes these initial functions so special?

[japplepie]

People say that if you could break a function down into these three functions (constant, successor, projection or sometimes called initial/basic functions) using some operators, then it is primitive recursive.

What makes these three functions so special?

 

[phinds]

People say that if you could break a function down into these three functions (constant, successor, projection or sometimes called initial/basic functions) using some operators, then it is primitive recursive.

What makes these three functions so special?

I don't know what you are talking about but I advise you that "people say ... " is just about the absolute worst reference you can use for this site and I suggest you get more specific.

 

[japplepie]

I don't know what you are talking about but I advise you that "people say ... " is just about the absolute worst reference you can use for this site and I suggest you get more specific.

Kleene said; http://plato.stanford.edu/entries/recursive-functions/#1.1

 

[phinds]

Again, I don't know anything about what you are talking about but I was struck by the fact that in your second post it became clear that you are talking about recursive functions whereas in your initial post there was not a hint of that. Perhaps people who are familiar w/ the characteristics of functions are automatically flagged by terms like "initial function" to know you are talking about recursive functions but I never would have guessed it.

My point is simply that the more clarity you can bring to your questions, the more likely you are to get helpful answers.

 

[jbriggs444]

I am having trouble understanding the thrust of the question. The definition for primitive recursive function is cast in terms of the constant function, the successor function and the projection function. That does not make those functions "special". They are simply the functions that happened to be used in the definition.

Perhaps a better phrasing is: "Why is the definition the way it is -- why choose those functions as building blocks?"

One answer to that is easy: Because they are about as simple a set of building blocks as it is possible to imagine. And, because, in conjunction with composition and recursion, they give about as much power as it is possible to have without being so powerful that undecidability becomes an issue.

Like phinds, I have no particular expertise in this area. Just muttering stuff that seems blatantly obvious.