MHB Can We Enumerate All Primitive Recursive Functions?

AI Thread Summary
Primitive recursive functions can be enumerated by listing all possible derivations and definitions. This enumeration is relevant in demonstrating that Ackermann's function is not primitive recursive. The proof of Ackermann's non-primitive recursive status involves showing properties applicable to all primitive recursive functions through this enumeration. The discussion clarifies that enumeration includes all basic functions and their definitions through compositions or primitive recursions. Understanding this enumeration is crucial for exploring the boundaries of primitive recursive functions.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

Can we enumerate the primitive recursive functions?
 
Physics news on Phys.org
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?
 
Yes.
 

Thread 'Formal derivation of statement from Peano Arithmetic system'

I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
View full post »

Similar threads

MHB Recursive and Primitive recursive functions
Replies
5
Views
3K
I Is the Inverse Image of a Computable Function Recursively Enumerable?
Replies
3
Views
2K
MHB Propositions for recursive functions
Replies
18
Views
4K
MHB Primitive recursive functions/sets
Replies
6
Views
2K
MHB Showing the nth prime is primitive recursive
Replies
1
Views
5K
There are effectively computable numerical functions which aren’t prim
Replies
1
Views
1K
I Explaining Enumerable: Understanding the Concept in Godel, Escher, Bach
Replies
6
Views
2K
MHB Points about the Ackermann's function
Replies
16
Views
4K
MHB Ackermann's function is μ-recursive
Replies
11
Views
4K
I Questions Regarding Primitive Unit Cell
Replies
4
Views
4K

Hot Threads

Recent Insights

Back
Top