MHB Can We Enumerate All Primitive Recursive Functions?

[mathmari]

Hey!

Can we enumerate the primitive recursive functions?

 

[Evgeny.Makarov]

Of course, just enumerate all possible derivations (definitions).

 

[mathmari]

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?

 

[Evgeny.Makarov]

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.

 

[mathmari]

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?

 

[Evgeny.Makarov]

Yes.