Can We Enumerate All Primitive Recursive Functions?

5 replies · 2K views · last reply
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

Can we enumerate the primitive recursive functions?
 
Of course, just enumerate all possible derivations (definitions).
 
Is the enumeration of primitve recursive functions an other way to show that Ackermann's function is not primitive recursive? Or isn't it possible?
 
In the proof that Ackermann's function is not p.r. you prove something for all p.r. functions, and you do this by enumerating all possible derivations.
 
Evgeny.Makarov said:
In the proof that Ackermann's function is not p.r. you prove something for all p.r. functions, and you do this by enumerating all possible derivations.

By "enumerating all possible derivations" do you mean that we enumerate all possible cases how the p.r. function is defined, if it is one of the basic functions (constant, successor, projection), or is defined by compositions or primitive recursions?